[알고리즘] 최소 신장 트리(MST)와 크루스칼 알고리즘

MST와 크루스칼 알고리즘 동작 원리. "최소 비용으로 모두 연결"이라는 키워드에서 어떻게 크루스칼까지 이어지는지, 왜 싼 간선부터 고르면 항상 최솟값이 보장되는지 추적해봤다.

---

1. MST란?

핵심 아이디어

모든 노드를 사이클 없이 최소 비용으로 연결한 트리

MST(Minimum Spanning Tree, 최소 신장 트리)는 알고리즘이 아니라 개념이다. "모든 노드를 연결하는 트리 중 간선 비용의 합이 가장 작은 것"을 의미한다.

문제에서 아래 키워드가 보이면 MST를 떠올려야 한다.

• "최소 비용으로 모두 연결"
• "모든 섬/도시/노드를 잇는 최소 비용"

그림 1. MST 예시 — 섬 연결하기

      1
  0 ----- 1
  |        |
2 |        | 1
  |        |
  2        3

간선 목록: [0-1: 1], [0-2: 2], [1-2: 5], [1-3: 1], [2-3: 8]
MST 선택:  [0-1: 1], [1-3: 1], [0-2: 2]  → 총 비용 4

---

2. 사이클이란?

크루스칼을 이해하려면 사이클 개념이 먼저다.

사이클 = 출발점으로 다시 돌아오는 경로

그림 2. 사이클 있는 경우 vs 없는 경우

# 사이클 있음 (0→1→2→0 으로 순환)
0 - 1
|   |
2 --+

# 사이클 없음 (트리)
0 - 1
|
2

MST는 트리이기 때문에 사이클이 존재하면 안 된다. 사이클이 생긴다는 건 "이미 다른 경로로 연결되어 있는데 또 연결하는 것" = 낭비다.

---

3. 크루스칼 알고리즘

MST를 구현하는 대표적인 방법이 크루스칼 알고리즘이다.

핵심 전략

싼 간선부터 골라서, 사이클이 안 생기면 연결한다

그림 3. 크루스칼 동작 흐름

① 간선을 비용 기준 오름차순 정렬
   [0-1:1] [1-3:1] [0-2:2] [1-2:5] [2-3:8]

② 하나씩 꺼내면서
   사이클 X → 연결 + 비용 누적
   사이클 O → 스킵

[0-1:1] → 연결  total=1   {0,1}, {2}, {3}
[1-3:1] → 연결  total=2   {0,1,3}, {2}
[0-2:2] → 연결  total=4   {0,1,2,3}
[1-2:5] → 스킵 (0,1,2 이미 같은 그룹)
[2-3:8] → 스킵 (모두 같은 그룹)

③ 결과: 총 비용 4

---

4. 왜 싼 것부터 고르면 항상 최솟값이냐?

외우지 말고 직관적으로 이해해보자.

그림 4. 비싼 간선은 항상 더 싼 걸로 대체 가능

노드: X, Y, Z
간선: A=X-Y(1), B=Y-Z(2), C=X-Z(10)

경우 1 (싼 것부터): A + B = 1 + 2 = 3
      X - Y - Z

경우 2 (비싼 것 포함): A + C = 1 + 10 = 11
      X - Y
      |
      Z

→ C 대신 B를 쓰면 무조건 더 싸다
→ 비싼 간선은 항상 더 싼 대안으로 대체 가능

단, 조건이 하나 있다. 사이클이 생기지 않을 때만!

사이클이 생긴다는 건 해당 간선이 없어도 이미 연결되어 있다는 뜻이므로, 그 간선은 쓸모없는 낭비다.

---

5. 사이클 감지 — 왜 Union-Find가 필요한가?

크루스칼을 구현하려면 매 간선마다 "이 간선을 추가하면 사이클이 생기나?" 를 판단해야 한다.

표 1. 사이클 감지 방법 비교

방법 동작 시간복잡도

리스트로 그룹 관리	전체 탐색으로 소속 확인	O(N)
Union-Find	parent 배열 인덱스 접근	O(α(N)) ≈ O(1)

리스트 방식은 동작은 하지만 느리다. 섬이 수백 개면 매번 전체를 뒤져야 한다.

Union-Find는 각 노드에 "부모 번호 하나" 만 저장해서 같은 그룹인지를 거의 O(1)에 판단한다.

Union-Find 동작 원리 상세 설명 → 유니온-파인드(Union-Find)로 집합 관리하기

---

6. 전체 흐름 추적

costs = [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]], 섬 4개

데이터 1. 정렬 후 간선 처리 흐름

# 정렬 후
costs = [[0,1,1],[1,3,1],[0,2,2],[1,2,5],[2,3,8]]

# 초기 상태
parent = [0, 1, 2, 3]
rank   = [0, 0, 0, 0]
total  = 0

데이터 2. 간선별 처리 결과

[0,1,1] find(0)=0, find(1)=1 → 다름 → union → parent=[0,0,2,3] total=1
[1,3,1] find(1)=0, find(3)=3 → 다름 → union → parent=[0,0,2,0] total=2
[0,2,2] find(0)=0, find(2)=2 → 다름 → union → parent=[0,0,0,0] total=4
[1,2,5] find(1)=0, find(2)=0 → 같음 → 스킵
[2,3,8] find(2)=0, find(3)=0 → 같음 → 스킵

결과: 4

---

7. 최종 코드

코드 1. 크루스칼 + Union-Find 전체 코드

def find(x, parent):
    if parent[x] != x:
        parent[x] = find(parent[x], parent)
    return parent[x]


def union(a, b, cost, parent, rank):
    root_a = find(a, parent)
    root_b = find(b, parent)

    if root_a != root_b:
        if rank[root_a] > rank[root_b]:
            parent[root_b] = root_a
        elif rank[root_a] < rank[root_b]:
            parent[root_a] = root_b
        else:
            parent[root_b] = root_a
            rank[root_a] += 1
        return cost  # 연결 성공 → 비용 반환
    return 0         # 사이클 → 스킵


def solution(n, costs):
    parent = list(range(n))
    rank = [0] * n
    total = 0

    costs.sort(key=lambda x: x[2])  # 비용 오름차순 정렬

    for a, b, cost in costs:
        total += union(a, b, cost, parent, rank)

    return total

---

8. 문제 보고 크루스칼 떠올리는 사고 흐름

그림 5. 키워드 → 알고리즘 연결 흐름

"최소 비용으로 모두 연결"
        ↓
      MST 개념
        ↓
   크루스칼 알고리즘
   (싼 간선부터 정렬)
        ↓
  사이클 판단 필요
        ↓
    Union-Find

표 2. 문제 키워드별 알고리즘 매핑

문제 키워드 떠올릴 것

최소 비용으로 모두 연결	MST → 크루스칼 → Union-Find
그룹 묶기, 같은 집합 판단	Union-Find
최단 경로 (1:1)	다익스트라
연결 여부 탐색	BFS/DFS

---

9. 시간복잡도

표 3. 크루스칼 시간복잡도

단계 시간복잡도

간선 정렬	O(E log E)
Union-Find (E번)	O(E · α(N)) ≈ O(E)
전체	O(E log E)

E = 간선 수, N = 노드 수, α = 아커만 역함수 (사실상 상수)

정렬이 병목이므로 전체 시간복잡도는 **O(E log E)**다.

---

10. 이 알고리즘을 적용한 문제

크루스칼 + Union-Find를 직접 구현해 푼 문제 풀이는 아래 포스팅에서 확인할 수 있다.

• [프로그래머스] 섬 연결하기 - Level 3 (Python)

---

🏷️ 태그

#알고리즘 #MST #최소신장트리 #크루스칼 #Kruskal #유니온파인드 #코딩테스트 #그래프 #파이썬