2. 최단 경로 (다익스트라)

DFS/BFS 챕터에서 미로 최단거리는 BFS로 풀었죠. "가까운 칸부터 물결처럼 퍼지니까, 어떤 노드에 처음 도달한 순간이 곧 최단거리"라는 논리였습니다. 그런데 이 논리에는 숨은 전제가 하나 있었어요. 모든 이동 비용이 1로 같을 때만 성립한다는 겁니다. 도로마다 거리가 다르고, 통행료가 다르다면? 한 걸음 = 한 칸이라는 등식이 깨지면서 BFS로는 최단거리를 구할 수 없습니다. 이럴 때 쓰는 게 바로 다익스트라(Dijkstra) 예요.

이 한 챕터에서 배우는 것:

BFS가 안 통하는 순간: 간선마다 비용이 다르면 왜 물결이 깨지는지
최소 힙(heapq) 으로 "가장 가까운 노드부터 확정"하는 원리
가중치 있는 인접 리스트와 dist 배열, heapq 완성 코드
시간복잡도 O(E log V) 와 다익스트라의 한계(음수 간선)

BFS가 무너지는 순간

간단한 예를 봅시다. 0번에서 2번으로 가는 최단 비용을 구한다고 할게요.

0 → 2 : 비용 10 (직행)
0 → 1 : 비용 1
1 → 2 : 비용 1

BFS 눈으로 보면 2번은 0번에서 간선 하나로 바로 닿습니다. 그러니 BFS는 "2번은 1걸음, 도달 완료!"라고 비용 10을 확정해버려요. 하지만 실제 최단은 0 → 1 → 2 = 1 + 1 = 2 입니다. 간선 개수(걸음 수)와 실제 비용이 따로 놀기 때문에 BFS의 "먼저 도달 = 최단" 논리가 깨지는 거죠.

💡 핵심은 이겁니다. BFS는 걸음 수를 기준으로 물결을 퍼뜨립니다. 간선 비용이 전부 1이면 걸음 수 = 비용이라 맞아떨어지지만, 비용이 제각각이면 걸음 수로 줄 세운 순서가 비용 순서와 어긋납니다.

아이디어: 가장 가까운 노드부터 확정하기

그럼 어떻게 고칠까요? BFS가 "걸음 수가 작은 것부터" 큐에서 꺼냈다면, 다익스트라는 "지금까지 알아낸 비용이 가장 작은 노드부터" 꺼냅니다.

왜 이게 통할까요? 아직 확정 안 된 노드들 중 비용이 가장 작은 노드를 골랐다면, 그 노드는 더 이상 줄어들 수 없습니다. 다른 경로로 돌아가면 이미 그 노드보다 비용이 큰 노드를 거쳐야 하는데, (음수 간선이 없다면) 거기서 비용이 더 붙지 줄지는 않으니까요. 그러니 가장 싼 노드를 꺼내는 순간 그 값은 최종 확정입니다. 이게 다익스트라의 심장이에요.

그런데 "아직 확정 안 된 노드 중 최솟값"을 매번 찾으려면 전부 훑어야 하니 느립니다. 여기서 최소 힙이 등장합니다.

💡 최소 힙 = 항상 최솟값이 먼저 나오는 큐. 아무 순서로 값을 넣어도 꺼낼 때는 늘 가장 작은 값이 나옵니다. 파이썬은 heapq 모듈로 제공하고, 넣기·빼기 모두 O(log n) 이에요. 우리가 원하던 "가장 가까운 노드부터"에 딱 맞는 도구죠.

heapq 30초 사용법

리스트 하나를 힙처럼 다루는 함수 두 개만 알면 됩니다.

import heapq

h = []
heapq.heappush(h, 5)     # 넣기
heapq.heappush(h, 1)
heapq.heappush(h, 3)

print(heapq.heappop(h))  # 1  (항상 최솟값이 먼저!)
print(heapq.heappop(h))  # 3
print(heapq.heappop(h))  # 5

튜플을 넣으면 첫 번째 원소 기준으로 정렬됩니다. 그래서 다익스트라에서는 (비용, 노드) 순서로 넣어요. 비용이 앞에 와야 "비용이 가장 작은 노드"가 먼저 나오니까요.

import heapq

h = []
heapq.heappush(h, (7, 'B'))   # (비용, 노드)
heapq.heappush(h, (2, 'A'))
heapq.heappush(h, (5, 'C'))

print(heapq.heappop(h))  # (2, 'A')  (비용 2가 가장 작음)

그래프 표현: 가중치 있는 인접 리스트

DFS/BFS 챕터의 인접 리스트에 비용만 얹으면 됩니다. 이웃을 그냥 노드가 아니라 (이웃, 비용) 튜플로 담는 거예요.

# graph[u] = [(v, w), ...]  =  u에서 v로 비용 w로 갈 수 있다
graph = {
    0: [(1, 1), (2, 10)],   # 0 → 1 (비용1),  0 → 2 (비용10)
    1: [(2, 1)],            # 1 → 2 (비용1)
    2: [],
}

dist 배열은 시작점에서 각 노드까지의 최소 비용을 기록합니다. 아직 모르니 처음엔 전부 무한대(inf)로 두고, 시작점만 0으로 시작해요. BFS의 visited/dist 배열과 역할이 같습니다. 다만 여기선 "도달했나?"가 아니라 "얼마에 도달했나?"를 기록하죠.

다익스트라 완성 코드

import heapq

def dijkstra(graph, start, n):
    INF = float('inf')
    dist = [INF] * n            # 시작점~각 노드 최소 비용, 처음엔 무한대
    dist[start] = 0             # 시작점은 0
    pq = [(0, start)]           # (비용, 노드) 최소 힙

    while pq:
        cost, u = heapq.heappop(pq)   # 지금 가장 싼 노드를 꺼냄 = 확정

        if cost > dist[u]:            # 이미 더 싼 경로로 확정된 노드면 건너뜀
            continue

        for v, w in graph[u]:         # u의 이웃 v를 비용 w로
            new_cost = cost + w       # u까지 온 비용 + u→v 비용
            if new_cost < dist[v]:    # 더 싼 길을 찾았으면
                dist[v] = new_cost    # 갱신하고
                heapq.heappush(pq, (new_cost, v))  # 힙에 넣어 다시 검토

    return dist

graph = {
    0: [(1, 1), (2, 10)],
    1: [(2, 1)],
    2: [],
}
print(dijkstra(graph, 0, 3))   # [0, 1, 2]

결과 [0, 1, 2]를 보세요. 2번까지의 최단 비용이 (직행 10이 아니라) 0 → 1 → 2의 2로 제대로 나왔습니다. BFS가 틀렸던 바로 그 문제를 다익스트라가 맞힌 거예요.

동작을 따라가 봅시다.

힙 [(0,0)]. (0,0) 꺼냄. 이웃 갱신: dist[1]=1, dist[2]=10. 힙 [(1,1),(10,2)].
(1,1) 꺼냄(더 쌈). 이웃 2 갱신: 1+1=2 < 10 → dist[2]=2. 힙 [(2,2),(10,2)].
(2,2) 꺼냄. 2번 확정(비용 2).
(10,2) 꺼냄. 그런데 10 > dist[2]=2 → 건너뜀. 끝.

💡 4번의 if cost > dist[u]: continue가 중요합니다. 힙에는 갱신되기 전의 낡은 (10,2) 같은 값이 그대로 남아 있어요. 지우지 않고, 꺼낼 때 "이미 더 싼 값이 있네" 하고 무시합니다. 이걸 "lazy deletion(게으른 삭제)"이라 부르고, 이 한 줄이 없으면 이미 확정된 노드를 다시 처리해 느려집니다.

시간복잡도와 한계

힙에 들어가는 원소는 최대 간선 수(E) 만큼이고, 힙 연산 하나가 O(log V) (V는 노드 수)입니다. 그래서 전체는 O(E log V).

노드 1만 개, 간선 10만 개짜리 그래프도 대략 100,000 × 17 ≈ 170만 번. 복잡도 챕터의 "1초 ≈ 1억 번" 기준으로 여유입니다.

한 가지 함정. 다익스트라는 음수 간선이 있으면 쓸 수 없습니다. "가장 싼 노드를 꺼내면 그 값은 확정"이라는 논리가, 나중에 음수 간선으로 비용이 더 줄어들 수 있으면 무너지기 때문이에요. 음수 간선이 있는 그래프의 최단 경로는 벨만-포드(Bellman-Ford) 같은 다른 알고리즘을 써야 합니다.

💡 판단 기준. 가중치가 있고 전부 0 이상이면 다익스트라, 가중치가 전부 1이면 (더 간단한) BFS, 음수 간선이 섞였으면 벨만-포드. 대부분의 코딩테스트 최단경로 문제는 다익스트라로 풀립니다.

정리

상황	알고리즘	자료구조	시간복잡도
간선 비용이 전부 1	BFS	큐(`deque`)	O(V + E)
간선 비용이 제각각(0 이상)	다익스트라	최소 힙(`heapq`)	O(E log V)
음수 간선이 있음	벨만-포드	배열	O(V · E)

💡 다익스트라를 한 문장으로. "BFS의 큐를 최소 힙으로 바꾸고, 걸음 수 대신 누적 비용으로 줄 세운 것." BFS를 알면 다익스트라는 절반 이해한 겁니다. 나머지 절반이 (비용, 노드) 힙과 lazy deletion 한 줄이에요.

직접 풀어보기

위 dijkstra로 다음 그래프에서 0번 출발 최단거리를 구해보세요. {0:[(1,4),(2,1)], 1:[(3,1)], 2:[(1,2),(3,5)], 3:[]} (정답: [0, 3, 1, 4]. 0→2→1→3 = 1+2+1)
dijkstra가 반환한 dist에서 도달 불가능한 노드는 어떤 값으로 남을까요? 그 노드로 가는 간선이 하나도 없는 그래프를 만들어 확인해보세요. (힌트: float('inf'))
최단 비용뿐 아니라 실제 경로(거쳐온 노드 순서) 도 구하려면? parent[v] = u 배열을 두고, dist[v]를 갱신할 때 parent[v] = u도 같이 기록한 뒤 도착점부터 거꾸로 따라가 보세요.