모든 도시를 가장 싸게 잇는 길
여러 도시를 케이블로 모두 연결한다고 해봅시다. 케이블마다 비용이 다르고, 예산은 빠듯합니다. 모든 도시가 끊김 없이 이어지되, 전체 케이블 비용은 최소가 되게 하려면 어떤 케이블을 깔아야 할까요?
이렇게 "모든 노드를 사이클 없이, 최소 비용으로 잇는" 트리를 최소 신장 트리(MST, Minimum Spanning Tree) 라고 합니다. 노드가 \(V\)개면 정확히 \(V-1\)개의 간선으로 모두 연결되죠.
예: A·B·C·D·E·F 6개 도시를 잇는 MST의 총 비용이 19라면, 그 19를 만드는 간선 5개를 골라내는 게 목표입니다.
MST를 구하는 대표 알고리즘은 두 가지입니다. 가장 싼 간선부터 정렬해 훑는 크루스칼, 그리고 오늘 볼 프림입니다.
프림은 어떻게 접근할까? (핵심 아이디어)
크루스칼이 "간선을 전부 정렬해놓고 싼 것부터" 본다면, 프림은 다릅니다.
한 노드에서 출발해, 지금까지 만든 트리에 "가장 싸게 붙는 간선"을 하나씩 더해 트리를 키웁니다.
1. 시작 노드 하나를 트리에 넣는다
2. 트리에 붙일 수 있는 간선 중 가장 싼 것을 찾는다
3. 그 간선으로 새 노드 하나를 트리에 편입한다
4. 노드가 모두 들어올 때까지 2~3을 반복
마치 눈덩이를 굴리듯, 트리라는 한 덩어리가 매번 가장 싼 방향으로 한 칸씩 커집니다.
왜 하필 우선순위 큐로 '간선'을 고를까?
여기서 자연스러운 질문이 나옵니다. "트리에 붙일 수 있는 가장 싼 간선"을 매번 어떻게 빨리 찾지?
트리가 커질수록 트리 경계에 걸친 후보 간선은 계속 늘었다 줄었다 합니다. 매번 전부 훑으면 느립니다. 그래서 (간선 비용, 그 간선이 닿는 노드) 를 우선순위 큐(최소 힙) 에 넣어두고, 꺼낼 때 항상 가장 싼 것이 먼저 나오게 합니다. 새 노드를 편입할 때마다 그 노드의 이웃 간선들을 큐에 추가하면, 큐는 늘 "지금 트리에 붙일 수 있는 후보들"을 정렬된 상태로 들고 있게 됩니다.
각 노드마다 key[v] = "v를 현재 트리에 잇는 가장 싼 간선 비용"을 기억해두고, 더 싼 간선이 나타나면 줄여줍니다. 이 "더 싸지면 갱신"이 바로 완화(relaxation)입니다.
다익스트라랑 똑같은 거 아닌가요?
코드 모양은 정말 닮았습니다. 둘 다 우선순위 큐에서 (값, 노드)를 꺼내고, 이웃을 보며 값을 갱신하죠. 그런데 꺼내서 비교하는 '값'이 다릅니다.
| 다익스트라 | 프림 | |
|---|---|---|
| 큐에 넣는 값 | 시작점부터의 누적 거리 | 트리에 한 칸 붙이는 간선 1개의 비용 |
| 갱신 식 | dist[u] + w (경로 합) | w (간선 하나) |
| 구하는 것 | 한 점에서의 최단 경로 | 전체를 잇는 최소 트리 |
다익스트라는 "시작점까지 얼마나 멀리 왔나"의 합을 따지고, 프림은 "이 노드를 트리에 붙이는 간선 하나"가 얼마인지만 봅니다. 이 한 끗 차이가 결과를 최단 경로 vs 최소 신장 트리로 완전히 갈라놓습니다.
눈으로 보면 확실해집니다
말로 들으면 "거리 합이냐 간선 하나냐"가 헷갈리지만, 트리가 한 노드씩 커지고 우선순위 큐가 가장 싼 간선을 토해내는 장면을 보면 한 번에 와닿습니다.
알고노트에서는 6개 노드 그래프에서 프림이 시작 노드부터 트리를 키워가는 과정을, key 값 갱신과 우선순위 큐의 변화까지 단계별로 따라갈 수 있습니다. 어떤 간선이 선택되고 어떤 간선이 (이미 트리 안이라) 버려지는지, 최종 MST 비용이 어떻게 19가 되는지 직접 확인해보세요.