다익스트라 알고리즘 - 우선순위 큐와 방문 처리에 대해

다익스트라 문제를 풀다가 공식처럼 우선순위 큐를 사용하고, 방문 처리를 하는 느낌이 들었다. "우선순위 큐를 꼭 사용해야 하는가?", "방문 처리를 꼭 해야 하는가?" 라는 궁금증이 들어서 이 글을 작성한다.

 

https://www.acmicpc.net/problem/1753 이 문제를 예로 들자.

 

입력 값이 다음과 같고, 1번 노드에서 출발한다고 가정하자.

5 6
1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 1
4 5 2

 

간선을 리스트로 표현하면 다음과 같고,

 

1 ➡️ 2 ➡️ 3번 노드 순서로 방문했을 때의 모습은 다음과 같다.

 

이때 큐에는 (4, 7)과 (4, 4)가 담겨있다. (노드 4번까지 오는데 걸린 비용이 각각 7, 4)

• 우선순위 큐를 사용하지 않을 경우
  • (4, 7)을 먼저 poll한다. 그리고 cost[5]의 값은 7 + 2 = 9가 된다.
  • 이어서 (4, 4)를 poll하는데 이미 4번 노드는 방문처리가 되었으므로, continue한다.
  • 따라서 5번 노드까지의 최소 비용이 9가 된다. (cost[5] = 9)
• 우선순위 큐를 사용할 경우
  • (4, 4)를 먼저 poll한다. 그리고 cost[5]의 값은 4 + 2 = 6이 된다.
  • 이어서 (4, 7)을 poll하는데 이미 4번 노드에 대한 방문처리가 되었으므로 continue한다.
  • 따라서 5번 노드까지의 최소 비용이 6이 된다. (cost[5] = 6)

즉, 우선순위 큐를 사용하지 않으면서 방문처리를 하면, 이미 방문해서 더 적은 비용의 경로를 지나치게 된다. 따라서 올바른 답이 나오지 않는다.

 

반면, 우선순위 큐를 사용하면서 방문처리를 하면, 어차피 최단 비용의 경로를 먼저 poll하므로, 최단 비용의 경로에 대해 우선적으로 처리한다. 그리고 더 큰 비용의 경로에 대해서는 이미 방문처리가 되어있으므로 지나치게 된다. 따라서 우선순위 큐를 사용할 경우, 방문처리가 불필요하게 된다.

 

그리고 우선순위 큐를 사용하면 방문처리를 하지 않더라도, 시간초과가 나지 않는다. 어차피 최단 경로를 먼저 poll해서 처리하고, 그보다 큰 경로에 대해서는 cost 배열이 갱신되지 않으므로 que에 추가하지 않고, 따라서 언젠간 que가 비게 되기 때문이다.

 

정리하면 다음과 같다.

• 우선순위 큐를 사용하면서 방문처리를 하면 올바른 답이 나온다.
• 그런데, 우선순위 큐를 사용하면 방문처리를 하지 않아도 된다. 어차피 최단 경로를 먼저 poll해서 처리하고, 그보다 큰 경로에 대해서는 cost 배열이 갱신되지 않아 que에 추가되지 않는다. 따라서 언젠간 que가 비게 되어 시간초과가 나지 않는다.
• 방문처리를 하면서 우선순위 큐를 사용하지 않으면 올바른 답을 구하지 못한다. 이미 방문했다고 더 적은 비용의 경로를 지나칠 수 있기 때문이다.

따라서 최단경로를 구할 때는 우선순위 큐를 사용해서, 최단 경로에 대해 우선적으로 처리하자.