3개의 댓글이 있습니다.
-
-
JongMan -
2차원 배열 위에서 움직인다고 하면 인접 행렬이나 인접 리스트를 직접 만드실 필요가 없습니다. 좌표 (x, y)를 나타내는 각 정점을 만드는 대신, 각 정점을 그냥 좌표로 표현하면 됩니다. 이 때 그래프 구조는 코드에 직접 나타나지 않습니다. 이런 것을 암시적 (혹은 내재적?) 그래프 표현이라고 부릅니다.
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
lionix
현재 온라인 Judge에서 문제를 하나 보고 있는데
어떤 방식으로 접근해야할지 잘 몰라서 질문드립니다!
1 2 3 4 5
5 4 3 2 1
0 9 8 7 1
9 4 7 5 8
2 3 4 9 3
이정도의 각각의 어레이 내용에 비용이 있습니다.
맨 위 1,1 부터 끝점 5,5 까지의 최소합을 구하려면..
다이나믹을 이용하여 우아하게 구현이 가능하지만..
제가 원하는 좌표 x1,y1 -> x2, y2까지의 최소 비용을 구하려면
어떤 알고리즘으로 접근해야하는지 궁금합니다.
BFS(너비우선탐색)이나 다익스트라, 플로이드 알고리즘 등 여러개가 있는데
어레이의 크기가 100 by 100 정도만 되도 인접행렬에 관한 메모리 문제로
골치가 아프네요. 좋은 방법 있으면 조언 부탁드립니다. ^^
9년 전