알고스팟 - 1261
좌표계에서 다익스트라를 작성할 때, 더 편하다.
어떤 그래프의 노드 중 A, B, C라는 노드가 있다고하자. 어떤 시작점 노드가 있을 때
A까지 이동하는 최단거리를 2라고 하자.
B까지 이동하는 최단거리를 3라고 하자.
우선순위 큐는 이동하는 최단경로가 작은 순서대로 pop을 진행한다.
즉 A를 먼저 pop하고 후에 B를 pop 한다.
그리고 A, B는 C로 직접적으로 이동할 수 있는 간선이 있다고 하자. 이때
A와 C를 연결하는 간선의 비용을 4라고 하자.
B와 C를 연결하는 간선의 비용을 2라고 하자.
먼저 A가 pop 되었을 때, C까지 이동하는 최단거리는 2 + 4 = 6 으로 업데이트된다.
(여기서 B까지의 최단거리는 3이고 C까지의 최단거리는 6이므로, C보다 B가 먼저 pop된다)
후에 B가 pop 되었을 때, C까지 이동하는 최단거리는 3 + 2 = 5로 업데이트된다.
B까지 pop된 상황에서 우선순위 큐에는 C에 대한 정보가 2개 저장된다.
하나는 지금까지 C까지 이동했을 때의 거리가 6이라는 정보와
나머지 하나는 C까지 이동했을 때까지 거리가 5라는 정보이다.
이때 첫번째 C에 대한 정보는 최근에 업데이트 된 최단거리보다 크므로
C와 연결되어있는 간선을 순회하는 불필요한 행위를 못하게 해주어야 한다.
하지만, 해당 알고스팟 문제에서는 저 행위 자체가 불필요하다.
왜나하면 어떤 X라는 노드가 있다고 했을 때, a, b, c는 X와 연결되는 간선이 존재한다고 하자.
이때 a, b, c에서 X와 연결되는 간선의 비용은 항상 같다.
어떤 노드에서 이동한다고 해도 벽을 부수던가 말던가 둘 중 하나이기 때문이다.
( f(n): 어떤 시작점에서 노드 n까지 이동하는 최단거리 라고 정의하자. )
더 자세히 분석하면 우선순위 큐에서 a, b, c 순서로 pop 했다고 할 때,
f(a) <= f(b) <= f(c) 이다.
a, b, c 각각에서 X로 이동하는 최단거리는 모두
f(a), f(b), f(c) 또는 f(a)+1, f(b)+1, f(c)+1 이기 때문에
어떤 노드까지 이동하는데 드는 최단거리는 가장 먼저 업데이트된 값과 같다.
— 결론
이 점을 통해 더 간단하게 다익스트라를 수행할 수 있겠다.
다음은 이 점을 적용할 수 있는 문제들이다.
녹색 옷 입은 애가 젤다지? - 4485
미로만들기 - 2665