최소 스패닝 트리 문제를 읽을 때 가장 먼저 해야 할 일은 알고리즘 이름을 외워서 꺼내는 것이 아니라, 문제의 목표가 무엇인지 정확히 읽는 것입니다. 최단거리를 구하는지, 아니면 전체 연결 비용을 줄이는지부터 나눠야 합니다.
MST는 한 출발점에서 빨리 가는 문제가 아니라, 모든 정점을 사이클 없이 가장 싸게 연결하는 문제입니다.
먼저 최소 스패닝 트리가 무엇인지 짧고 정확하게 보자
최소 스패닝 트리(Minimum Spanning Tree)는 가중치가 있는 연결 무방향 그래프에서 모든 정점을 연결하되, 사이클 없이, 전체 간선 가중치 합이 가장 작은 트리입니다.
- 모든 정점을 연결해야 합니다.
- 사이클이 있으면 안 됩니다.
- 간선 비용의 총합이 가장 작아야 합니다.
여기서 중요한 것은 개별 정점까지의 거리가 아니라 전체 연결 비용의 합입니다. 이 차이를 놓치면 MST 문제를 최단거리 문제처럼 잘못 풀기 쉽습니다.
최단거리와 최소 스패닝 트리는 왜 다를까
두 문제는 둘 다 가중치 그래프를 다루지만, 최적화 목표가 다릅니다. 다익스트라는 보통 한 시작점에서 다른 정점까지 가는 거리를 최소화합니다. 반면 MST는 시작점이 중요하지 않고, 네트워크 전체를 가장 싸게 연결하는 것이 목표입니다.
- 최단거리 문제: 한 시작점에서 목적지까지 빠르게 가기
- MST 문제: 전체 연결 비용을 가장 싸게 만들기
예를 들어 도시 여러 개를 인터넷 선으로 모두 연결해야 한다면, 한 도시에서 다른 도시로 가장 빨리 가는 길보다 전체 공사비를 얼마나 줄이느냐가 더 중요합니다. 이런 문제는 MST 쪽 감각이 맞습니다.
문제에서 어떤 신호가 보이면 최소 스패닝 트리를 떠올려야 할까
- 모든 정점을 연결해야 한다는 문장이 나온다
- 간선마다 비용이 있고 총합 최소화가 핵심이다
- 출발점 하나보다 전체 네트워크 구성이 중요하다
- 사이클은 의미 없고 비용만 늘리는 구조처럼 보인다
- 도로, 전선, 네트워크, 파이프 연결 같은 비유가 나온다
반대로 특정 출발점에서 각 정점까지의 최소 비용, 최소 시간, 최소 거리 같은 문장이 중심이면 최단거리 문제일 가능성이 큽니다. 즉 무엇을 최소화하느냐가 가장 중요한 분기점입니다.
크루스칼은 어떤 흐름으로 움직일까
크루스칼은 간선 중심으로 생각합니다. 그래프 전체에서 가장 싼 간선부터 보면서, 현재 연결 구조를 망치지 않는 간선만 채택합니다.
- 모든 간선을 가중치 오름차순으로 정렬한다
- 가장 싼 간선부터 하나씩 본다
- 넣어도 사이클이 생기지 않으면 채택한다
- 사이클이 생기면 버린다
- 간선이 정점 수 – 1개가 되면 끝낸다
크루스칼의 핵심 질문은 매번 하나입니다. 이 간선을 넣으면 사이클이 생길까?
그래서 크루스칼은 유니온 파인드와 아주 잘 붙습니다. 두 정점이 이미 같은 연결 요소에 속하는지만 빠르게 판별하면 되기 때문입니다.
class DSU:
def __init__(self, n):
self.parent = list(range(n + 1))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
self.parent[rb] = ra
return True
def kruskal(n, edges):
edges.sort(key=lambda x: x[2])
dsu = DSU(n)
total = 0
chosen = []
for u, v, w in edges:
if dsu.union(u, v):
total += w
chosen.append((u, v, w))
if len(chosen) == n - 1:
break
return total, chosen이 코드는 길지 않지만 흐름이 분명합니다. 정렬이 먼저 나오고, 그 다음에는 매 간선마다 union 가능 여부만 검사합니다. 즉 정렬은 순서를 정하고, DSU는 채택 가능 여부를 판정합니다.
작은 예시로 크루스칼을 따라가 보자
정점이 4개이고 간선이 아래와 같다고 해 보겠습니다.
- 1-2 비용 1
- 2-3 비용 2
- 1-3 비용 3
- 3-4 비용 4
- 2-4 비용 5
정렬 후 순서는 이미 위와 같습니다. 먼저 1-2를 채택하고, 다음에 2-3을 채택하면 1,2,3이 하나의 덩어리가 됩니다. 그다음 1-3은 이미 같은 덩어리 안을 다시 잇기 때문에 사이클을 만들고 버립니다. 마지막으로 3-4를 채택하면 모든 정점이 연결됩니다.
이 예시가 중요한 이유는 가장 싼 간선을 무조건 넣는 것이 아니라, 현재 연결 구조를 망치지 않는 가장 싼 간선을 넣는 것이라는 점을 보여주기 때문입니다.
프림은 어떤 흐름으로 움직일까
프림은 간선 전체를 한꺼번에 정렬해서 보는 대신, 현재 만들어진 트리 바깥으로 가장 싸게 뻗는 간선을 계속 고릅니다. 즉 시야가 그래프 전체 간선이 아니라 현재 트리의 경계에 있습니다.
- 아무 정점 하나에서 시작한다
- 현재 트리와 연결되는 간선 중 가장 싼 간선을 고른다
- 트리에 없는 정점을 하나 새로 편입한다
- 모든 정점이 들어올 때까지 반복한다
그래서 프림은 우선순위 큐와 잘 붙습니다. 지금 당장 경계에 걸린 후보 간선 중 가장 싼 것을 빨리 꺼내야 하기 때문입니다.
import heapq
def prim(n, graph, start=1):
visited = [False] * (n + 1)
pq = [(0, start)]
total = 0
picked = 0
while pq and picked < n:
cost, node = heapq.heappop(pq)
if visited[node]:
continue
visited[node] = True
total += cost
picked += 1
for nxt, w in graph[node]:
if not visited[nxt]:
heapq.heappush(pq, (w, nxt))
return total프림 구현은 시작점이 있다는 점 때문에 얼핏 다익스트라처럼 보일 수 있습니다. 하지만 목표는 여전히 개별 최단거리가 아니라, 새 정점을 가장 싸게 편입해 전체 트리를 키우는 것입니다.
그럼 크루스칼과 프림 중 언제 무엇이 더 자연스러울까
- 간선 리스트가 이미 주어지고, 사이클 판별 중심으로 생각하기 쉽다면 크루스칼
- 현재 한 정점에서 시작해 인접 정점을 확장하는 흐름이 더 자연스럽다면 프림
- 유니온 파인드가 익숙하고 희소 그래프의 간선 정렬이 부담되지 않으면 크루스칼
- 우선순위 큐 기반 확장 흐름이 직관적이고 인접 리스트가 잘 준비되어 있으면 프림
입문 단계에서는 크루스칼은 간선 정렬 + 사이클 판별, 프림은 트리 확장 + 우선순위 큐라고 기억하면 충분합니다. 이 정도 프레임만 있어도 문제 읽는 속도가 크게 빨라집니다.
복잡도는 구현 세부에 따라 달라질 수 있지만, 실전에서는 크루스칼은 보통 정렬 비용이 앞에 있고, 프림은 우선순위 큐로 경계 간선을 관리한다고 이해하면 무난합니다.
입문자가 자주 하는 오해
- MST와 최단거리를 같은 문제라고 생각한다
- 가장 싼 간선은 무조건 넣는다고 생각한다
- 프림이 시작점이 있으니 최단거리 알고리즘과 같다고 느낀다
- 유니온 파인드가 MST를 만드는 알고리즘이라고 오해한다
유니온 파인드는 MST를 만드는 알고리즘이 아니라, 크루스칼이 매번 던지는 연결성 질문에 빠르게 답해 주는 도구입니다. 프림의 우선순위 큐도 마찬가지로, 프림 자체가 아니라 프림의 현재 경계 선택을 돕는 도구입니다.
마무리
- 문제의 목표가 전체 연결 비용 최소화인지 먼저 본다
- 그렇다면 MST 가능성을 먼저 의심한다
- 간선 정렬과 사이클 판별이 중심이면 크루스칼
- 현재 트리를 바깥으로 확장하는 흐름이면 프림
- 최단거리 문제와 혼동하지 않는 것이 가장 중요하다
유니온 파인드 자체가 아직 낯설다면 유니온 파인드: 왜 빠를까를 먼저 함께 보는 것이 좋습니다. 가중치가 있는 최단거리와 MST 차이를 더 분명히 잡고 싶다면 다익스트라 알고리즘 입문도 이어서 읽어볼 만합니다.
정의와 구현 흐름은 Princeton Algorithms의 MST 설명, cp-algorithms의 Kruskal with DSU, cp-algorithms의 Prim algorithm을 참고했습니다.
