Dijkstra visited 처리는 코딩테스트 구현에서 자주 헷갈리는 부분입니다. 어떤 코드는 visited 배열을 쓰고, 어떤 코드는 쓰지 않고, 또 어떤 코드는 우선순위 큐에 같은 정점을 여러 번 넣습니다.
핵심은 dist 배열이 현재까지 찾은 최단거리이고, heap에서 꺼낸 값이 dist보다 크면 오래된 후보라는 점입니다. 이 기준을 알면 visited를 언제 써도 되고 언제 생략해도 되는지 이해할 수 있습니다.
Dijkstra visited보다 먼저 볼 dist
다익스트라의 중심은 dist 배열입니다. dist[v]는 시작점에서 v까지 현재까지 알고 있는 가장 짧은 거리입니다. 알고리즘은 가장 짧아 보이는 후보를 우선순위 큐에서 꺼내고, 그 정점에서 갈 수 있는 다음 간선을 확인합니다.
여기서 중요한 점은 heap 안의 값이 항상 최신이라고 보장되지 않는다는 것입니다. 더 긴 거리로 넣어 둔 후보가 나중에 heap에서 나올 수 있습니다. 그 사이에 더 짧은 경로가 발견되면 dist는 이미 갱신되어 있습니다.
우선순위 큐에 중복이 생기는 이유
Python heapq 같은 기본 priority queue는 이미 들어간 원소의 우선순위를 직접 낮추는 decrease-key 연산을 제공하지 않습니다. 그래서 더 짧은 거리를 찾으면 같은 정점을 새 거리로 다시 push하는 방식이 흔합니다.
import heapq
def dijkstra(graph, start):
INF = 10**18
dist = [INF] * len(graph)
dist[start] = 0
heap = [(0, start)]
while heap:
cost, node = heapq.heappop(heap)
if cost > dist[node]:
continue
for next_node, weight in graph[node]:
next_cost = cost + weight
if next_cost < dist[next_node]:
dist[next_node] = next_cost
heapq.heappush(heap, (next_cost, next_node))
return distvisited 없이도 되는 구현
위 구현은 visited 배열이 없습니다. 대신 heap에서 꺼낸 cost가 dist[node]보다 크면 오래된 entry로 보고 건너뜁니다. 이 조건이 outdated entry 검사입니다.
이 방식에서는 같은 정점이 heap에 여러 번 들어가도 괜찮습니다. 가장 짧은 값이 먼저 처리되고, 더 긴 값은 나중에 나왔을 때 dist 비교에 걸려 버려집니다.
visited를 써도 되는 구현
visited를 쓰는 구현도 가능합니다. 우선순위 큐에서 어떤 정점이 처음 꺼내지는 순간, 음수 간선이 없는 다익스트라에서는 그 정점의 최단거리가 확정됩니다. 이때 visited[node] = True로 표시하고 이후 중복 entry를 건너뛰는 방식입니다.
다만 visited를 너무 일찍 표시하면 틀립니다. 정점을 heap에 넣는 순간 방문 처리하면 안 됩니다. 정점은 heap에서 가장 짧은 후보로 꺼냈을 때 확정되는 것이지, 발견되었다고 바로 확정되는 것이 아닙니다.
# 틀리기 쉬운 생각
# heap에 넣는 순간 visited[next_node] = True로 처리하면
# 나중에 더 짧은 경로가 나와도 막아버릴 수 있다.음수 간선이 있으면 왜 안 될까
다익스트라는 가장 짧아 보이는 후보를 먼저 확정해도 된다는 성질에 기대고 있습니다. 그런데 음수 간선이 있으면 나중에 돌아오는 경로가 기존 확정 거리보다 더 짧아질 수 있습니다.
그래서 음수 가중치가 있는 그래프에서는 다익스트라 대신 Bellman-Ford 같은 다른 알고리즘을 검토해야 합니다. 코딩테스트에서 간선 가중치 조건을 먼저 읽어야 하는 이유입니다.
체크리스트
- 간선 가중치가 음수가 아닌지 확인했다
- dist 배열을 INF로 초기화했다
- heap에는 거리와 정점을 함께 넣었다
- heap에서 꺼낸 cost가 dist보다 크면 건너뛰었다
- visited를 쓴다면 push 시점이 아니라 pop 시점에 처리했다
정리
다익스트라 visited는 필수 문법이 아닙니다. 우선순위 큐 구현에서는 dist 비교로 오래된 entry를 건너뛰는 방식이 많이 쓰입니다. visited를 쓰더라도 정점이 heap에서 꺼내지는 시점에 최단거리가 확정된다는 기준을 지켜야 합니다.
관련 글은 greedy 반례부터 봐야 하는 이유, DP에서 메모이제이션과 테이블 방식은 무엇이 다를까, BFS와 DFS는 언제 다르게 써야 할까를 함께 보면 좋습니다. 외부 기준은 cp-algorithms – Dijkstra, Python docs – heapq, Dijkstra’s algorithm를 확인했습니다.
