최소 신장 트리와 Union-Find — 가장 싸게 잇기, 그리고 거의 O(1)의 마법

모든 점을 잇되, 가장 싸게

도시들을 광케이블로 전부 연결하되 총 비용을 최소로 하려면? 모든 정점을 사이클 없이 잇는 부분 그래프가 신장 트리(spanning tree) 이고, 그중 간선 가중치 합이 최소인 것이 최소 신장 트리(MST) 입니다. 정점 $V$개를 잇는 트리는 정확히 $V-1$개의 간선을 가집니다. 클러스터 네트워크 설계, 근사 클러스터링, 회로 배선이 전부 이 문제입니다.

MST의 토대는 컷 정리(cut property): 그래프를 두 덩어리로 가르는 어떤 컷에서도, 그 컷을 건너는 가장 가벼운 간선은 반드시 어떤 MST에 포함됩니다. 크루스칼과 프림은 이 정리를 다르게 활용할 뿐입니다.

크루스칼 — 싼 간선부터, 사이클만 피해서

크루스칼은 단순합니다. 모든 간선을 가중치 오름차순으로 정렬한 뒤, 싼 것부터 보며 사이클을 만들지 않으면 채택합니다. $V-1$개를 모으면 끝. 아래에서 간선이 가벼운 순으로 검사되며, 트리를 잇는 간선은 초록으로 채택, 사이클을 만드는 간선은 빨강으로 버려지는 걸 보세요.

여기서 “사이클을 만드는가?“를 빠르게 판정하는 게 관건입니다 — 두 정점이 이미 같은 덩어리에 속하면 잇는 순간 사이클입니다. 이걸 거의 $O(1)$에 답하는 자료구조가 Union-Find입니다.

Union-Find — 분리 집합, 거의 상수 시간의 비밀

Union-Find(분리 집합, DSU) 는 두 연산만 합니다. find(x)(x가 속한 집합의 대표를 반환)와 union(x, y)(두 집합을 합침). 각 원소가 부모를 가리키는 숲(forest)으로, 같은 트리에 있으면 같은 집합입니다.

순진하게 하면 트리가 한 줄로 길어져 find가 $O(n)$이 됩니다. 두 가지 최적화가 이를 거의 상수로 만듭니다.

• union by rank/size: 항상 작은 트리를 큰 트리 밑에 붙여 높이 억제.
• 경로 압축(path compression): find 도중 거쳐 간 모든 노드를 루트에 직접 매답니다.

아래는 경로 압축의 마법입니다. 길게 늘어진 체인에서 find(A)를 호출하면, 거쳐 간 노드들이 전부 루트로 납작하게 재배치됩니다 — 다음 조회는 한 번에 끝.

두 최적화를 함께 쓰면 $m$번 연산의 총비용이 $O(m \cdot \alpha(n))$ — 여기서 $\alpha$는 역 아커만 함수로, 우주의 원자 수쯤 되는 $n$에서도 4 이하입니다. 사실상 상수입니다.

parent = list(range(n)); rank = [0]*n
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # 경로 압축(절반)
        x = parent[x]
    return x
def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False            # 이미 같은 집합 = 사이클
    if rank[ra] < rank[rb]: ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]: rank[ra] += 1
    return True

프림 — 한 덩어리를 키워나가기

프림은 다익스트라를 닮았습니다. 한 정점에서 시작해, 지금 트리에 닿는 가장 가벼운 간선을 힙으로 골라 트리를 키웁니다. $O(E \log V)$. 간선이 빽빽한(dense) 그래프에선 프림이, 듬성한(sparse) 그래프에선 크루스칼이 흔히 유리합니다.

	크루스칼	프림
접근	간선 정렬 → 사이클 회피	정점 트리 확장
핵심 구조	Union-Find	우선순위 힙
시간	$O(E \log E)$	$O(E \log V)$
유리한 곳	희소 그래프	밀집 그래프

flowchart LR
    K["크루스칼: 간선 정렬"] --> U["Union-Find로<br/>사이클 판정"]
    U --> M["V-1개 모으면 MST"]
    P["프림: 시작 정점"] --> H["힙에서 최소 닿는 간선"]
    H --> M

프로덕션에서 마주치는 함정

함정	증상	해법
union by rank 없이 경로압축만	일부 입력서 느림	둘 다 적용(rank/size + 압축)
find에서 재귀	큰 입력 스택 오버플로	반복 + 절반 경로압축
비연결 그래프에 MST	$V-1$개 못 모음	최소 신장 숲(컴포넌트별)
간선 가중치 동률	MST가 유일하지 않음	타이브레이크 규칙 고정(재현성)
Union-Find로 “연결 끊기” 시도	불가(합치기 전용)	삭제 필요하면 다른 구조(LCT 등)

면접/리뷰 단골 질문

• Q. MST 간선 수? → 항상 $V-1$. 사이클 없이 모두 연결.
• Q. 크루스칼이 사이클을 어떻게 빨리 판정? → Union-Find. 두 끝점이 같은 집합이면 사이클 → 버림.
• Q. Union-Find가 거의 O(1)인 이유? → union by rank + 경로 압축 → $O(\alpha(n))$, 역 아커만은 사실상 ≤4.
• Q. 크루스칼 vs 프림 선택? → 희소면 크루스칼, 밀집이면 프림. 간선이 이미 정렬돼 있으면 크루스칼 유리.
• Q. 컷 정리? → 어떤 컷이든 그 컷을 건너는 최소 간선은 어떤 MST에 포함된다. 두 알고리즘의 정당성 근거.

정리

• MST = 모든 정점을 사이클 없이 잇는 최소 비용 트리($V-1$ 간선). 토대는 컷 정리.
• 크루스칼(간선 정렬 + Union-Find로 사이클 회피) vs 프림(힙으로 트리 확장). 희소↔밀집으로 선택.
• Union-Find는 union by rank + 경로 압축으로 거의 상수($\alpha(n)$). 연결성 판정의 만능 도구.
• 합치기 전용이라 “끊기”는 못 한다 — 동적 연결 끊김엔 다른 구조가 필요.

그래프 순회·최단 경로에 이은 그래프 3부작의 마지막입니다. 여기서 쓴 “정렬 후 그리디”는 다음 동적 계획법·그리디 편에서 더 깊게 다룹니다.

</content>