최소신장트리 (MST)

관련 문제

문제	난이도	핵심
섬 연결하기	Lv.3	크루스칼 기본
네트워크	Lv.3	Union-Find
방의 개수	Lv.5	MST 응용

---

1. 개념

MST(Minimum Spanning Tree, 최소신장트리)는 그래프의 모든 노드를 연결하는 간선들 중 가중치 합이 최소인 트리다.

조건
1. 모든 노드가 연결되어 있어야 한다
2. 사이클이 없어야 한다
3. 간선의 가중치 합이 최소여야 한다

대표적인 알고리즘으로 크루스칼(Kruskal)과 프림(Prim)이 있다. 코테에서는 크루스칼을 더 많이 쓴다.

---

2. 동작 과정

크루스칼 알고리즘

1. 모든 간선을 가중치 기준 오름차순 정렬
2. 가중치가 작은 간선부터 선택
3. 선택한 간선이 사이클을 만들면 제외
4. N-1개의 간선이 선택될 때까지 반복

단계	선택 간선	가중치	사이클?	선택
1	A - B	1	❌	✅
2	B - C	2	❌	✅
3	A - C	3	✅ (이미 연결됨)	❌
4	C - D	4	❌	✅

N-1개 간선 선택 완료 → MST 완성

---

3. Union-Find (핵심 도구)

크루스칼에서 사이클 판별을 위해 Union-Find(분리 집합) 자료구조를 사용한다.

Find: 노드가 속한 집합의 루트 찾기
Union: 두 집합을 하나로 합치기

두 노드의 루트가 같으면 → 사이클 발생
두 노드의 루트가 다르면 → 연결 가능

---

4. 핵심 포인트 2가지

크루스칼은 간선 중심, 프림은 노드 중심

	크루스칼	프림
방식	간선을 정렬 후 선택	노드를 하나씩 확장
적합한 경우	간선이 적은 희소 그래프	간선이 많은 밀집 그래프
코테 빈도	높음	낮음

Union-Find에서 경로 압축을 써라

Find를 반복하면 트리가 깊어져서 느려질 수 있다. 경로 압축을 적용하면 거의 O(1)에 가깝게 빨라진다.

find(x) 호출 시 루트까지 거슬러 올라가면서
중간 노드들의 부모를 바로 루트로 연결

---

5. 시간복잡도

알고리즘	시간복잡도	비고
크루스칼	O(E log E)	간선 정렬이 병목
프림 (우선순위 큐)	O(E log V)	밀집 그래프에 유리

E = 간선 수, V = 노드 수

---

6. 주의사항

• 사이클 판별은 Union-Find로 해라. DFS로도 가능하지만 Union-Find가 훨씬 빠르다.
• 간선 수가 N-1개가 되면 종료해라. N개 노드를 연결하는 MST의 간선 수는 항상 N-1개다.
• 경로 압축을 적용해라. Union-Find에서 경로 압축 없이 쓰면 시간초과가 날 수 있다.
• 연결 그래프인지 확인해라. 모든 노드가 연결되지 않은 그래프에서는 MST가 존재하지 않는다.