4. 최소 신장 트리 (크루스칼)

지금까지 배운 걸 하나씩 떠올려 보세요. 정렬(정렬 활용), 그리디(탐욕법), 유니온 파인드(서로소 집합). 이 챕터는 새로운 개념을 배우기보다, 이미 배운 세 도구를 합쳐서 하나의 알고리즘을 완성하는 이야기입니다. 그 결과물이 바로 크루스칼 알고리즘이에요. "정렬 + 그리디 + 유니온 파인드 = 크루스칼", 이 한 줄을 몸에 새기고 가면 됩니다.

이 한 챕터에서 배우는 것:

• 최소 신장 트리(MST) 가 뭔지: 모든 도시를 최소 비용 도로로 잇기
• 간선을 비용 오름차순으로 정렬하는 그리디 발상
• 사이클 판정에 유니온 파인드를 쓰는 이유
• 세 도구를 합친 크루스칼 완성 코드와 시간복잡도 O(E log E)

최소 신장 트리가 뭐죠?

도시가 여러 개 있고, 도시 사이에 도로를 놓을 수 있습니다. 각 도로는 건설 비용이 다릅니다. 목표는 모든 도시가 서로 연결되도록 하되, 총 건설 비용을 최소로 하는 것입니다.

여기서 두 가지 조건이 나와요.

• 모든 도시가 연결되어야 한다 (어느 도시에서든 다른 도시로 갈 수 있어야 함)
• 비용이 최소여야 한다 (필요 없는 도로는 놓지 않는다)

이렇게 "모든 노드를 잇는 최소 비용의 연결 구조"를 최소 신장 트리(MST, Minimum Spanning Tree) 라고 부릅니다. 여기서 신장(Spanning) 은 "모든 노드를 덮는다"는 뜻이고, 트리(Tree) 인 이유는 결과에 사이클이 없기 때문이에요.

💡 왜 트리(사이클 없음)일까요? 도시 A-B-C가 이미 연결됐는데 A와 C를 잇는 도로를 또 놓으면? 이미 A에서 C로 갈 수 있으니 그 도로는 비용 낭비입니다. 즉 최소 비용을 원하면 사이클은 저절로 사라져요. 노드가 N개면 MST의 간선은 항상 정확히 N-1개입니다.

위 그래프에서 4개 노드를 잇는 최소 비용은 간선 A-B(1), B-D(2), A-C(3)를 골라 1+2+3 = 6입니다. 어떻게 이걸 기계적으로 찾을까요?

발상: 싼 도로부터 욕심내서 고르자 (그리디)

가장 자연스러운 욕심은 이겁니다. "제일 싼 도로부터 하나씩 놓자."

이건 정확히 그리디의 사고방식이에요. 매 순간 "지금 가장 싼 간선"을 고르는 거죠. 그리고 그리디는 대부분 정렬에서 시작한다고 배웠습니다. 그래서 첫 단계는 정해졌어요. 모든 간선을 비용 오름차순으로 정렬합니다.

그런데 싼 것부터 무작정 고르면 문제가 생깁니다. 이미 연결된 도시들 사이에 또 도로를 놓으면 사이클이 생기고, 그건 비용 낭비였죠. 그래서 규칙을 하나 붙입니다.

싼 간선부터 순서대로 보되, 그 간선이 사이클을 만들면 버리고, 안 만들면 채택한다.

이게 크루스칼 알고리즘의 전부입니다. 다시 정리하면:

1. 모든 간선을 비용 오름차순 정렬 (← 정렬)
2. 싼 것부터 하나씩 보며 (← 그리디)
3. 사이클이 안 생기면 채택, 생기면 버림
4. 간선을 N-1개 채택하면 끝

남은 문제: "사이클이 생기나?"를 어떻게 판단하지?

3번이 핵심입니다. 간선 하나를 새로 놓았을 때 사이클이 생기는지 어떻게 알까요?

간선 u - v를 놓기 전에, u와 v가 이미 서로 연결되어 있다면 이 간선은 사이클을 만듭니다. 이미 길이 있는데 또 잇는 거니까요. 반대로 아직 연결 안 됐다면 안전하게 채택하면 됩니다.

"두 노드가 같은 그룹(연결된 덩어리)에 속하는가?" — 이거 어디서 본 질문 아닌가요? 바로 유니온 파인드가 하는 일입니다!

• find(u) == find(v) → 같은 그룹 → 이미 연결됨 → 채택하면 사이클 → 버린다
• find(u) != find(v) → 다른 그룹 → 채택하고 union(u, v)로 두 그룹을 합친다

이렇게 마지막 퍼즐 조각이 유니온 파인드로 딱 맞아떨어집니다. 앞 챕터에서 만든 도구가 여기서 그대로 재료가 되는 거예요.

💡 크루스칼이 세 개념의 "종합 예제"인 이유가 이겁니다. 정렬로 순서를 만들고, 그리디로 싼 것부터 집고, 유니온 파인드로 사이클을 걸러낸다. 하나라도 안 배웠으면 못 만드는데, 여러분은 이미 셋 다 배웠어요.

유니온 파인드 복습

크루스칼에 필요한 유니온 파인드를 짧게 다시 봅니다. parent[x]는 x의 대표(부모)를 가리키고, 경로 압축으로 find를 빠르게 만듭니다.

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 경로 압축
    return parent[x]

def union(parent, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra != rb:
        parent[rb] = ra   # b의 대표를 a의 대표 밑으로

parent = list(range(5))     # 0~4가 각자 자기 그룹 [0,1,2,3,4]
union(parent, 0, 1)
union(parent, 2, 3)
print(find(parent, 0) == find(parent, 1))   # True  (같은 그룹)
print(find(parent, 0) == find(parent, 2))   # False (다른 그룹)

크루스칼 완성 코드

이제 세 도구를 하나로 합칩니다. 간선은 (비용, u, v) 형태로 두면, 파이썬 정렬이 비용 기준으로 자동 정렬해 줘서 편해요.

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

def kruskal(n, edges):
    # n: 노드 개수(0 ~ n-1), edges: (비용, u, v) 리스트
    parent = list(range(n))
    edges.sort()              # ① 비용 오름차순 정렬 (튜플 첫 원소 기준)

    total = 0                 # MST 총비용
    used = 0                  # 채택한 간선 수
    for cost, u, v in edges:  # ② 싼 것부터 하나씩 (그리디)
        ru, rv = find(parent, u), find(parent, v)
        if ru != rv:          # ③ 다른 그룹이면 = 사이클 안 생김
            parent[rv] = ru   #    두 그룹을 합치고
            total += cost     #    이 간선을 채택
            used += 1
            if used == n - 1: # ④ 간선 N-1개 모으면 완성
                break
    return total

edges = [
    (1, 0, 1),   # A-B, 비용 1
    (3, 0, 2),   # A-C, 비용 3
    (2, 1, 3),   # B-D, 비용 2
    (4, 2, 3),   # C-D, 비용 4
]
print(kruskal(4, edges))   # 6   (1 + 2 + 3)

돌아가는 과정을 따라가 볼까요? 정렬하면 [(1,0,1), (2,1,3), (3,0,2), (4,2,3)] 순서가 됩니다.

• (1, 0, 1): 0과 1은 다른 그룹 → 채택 (누적 1), 그룹 {0,1}
• (2, 1, 3): 1과 3은 다른 그룹 → 채택 (누적 3), 그룹 {0,1,3}
• (3, 0, 2): 0과 2는 다른 그룹 → 채택 (누적 6), 그룹 {0,1,2,3} → 간선 3개 = N-1개, 끝!
• (4, 2, 3): 볼 필요도 없이 종료

가장 비싼 간선 4는 자연스럽게 버려졌습니다. 싼 것부터 골랐더니 최적이 나왔어요.

시간복잡도

무엇이 가장 오래 걸릴까요? 정렬입니다.

• 간선 정렬: 간선이 E개면 O(E log E)
• 간선을 한 번씩 훑으며 find/union: 유니온 파인드는 사실상 상수 시간에 가까워서 전체 O(E) 수준

둘을 합치면 정렬이 지배해서 O(E log E) 입니다.

💡 "간선을 한 번 정렬하고, 한 번 훑는다." 크루스칼의 비용은 사실상 정렬 비용이에요. 그래서 간선 수 E가 아주 많지만 않으면 아주 빠릅니다. 1초 ≈ 1억 번 기준으로, 간선 수십만 개도 여유롭게 처리합니다.

정리

💡 크루스칼은 새 알고리즘이라기보다 이미 배운 것들의 조립입니다. 앞으로도 어려워 보이는 알고리즘의 상당수는 "아는 도구 두세 개의 조합"이에요. 크루스칼이 그 첫 경험이 되면 좋겠습니다.

직접 풀어보기

1. 위 kruskal 함수에서 채택될 때마다 print(cost, u, v)를 찍어, 어떤 간선이 어떤 순서로 뽑히는지 눈으로 확인해 보세요. (정답 순서: 1 0 1 → 2 1 3 → 3 0 2)
2. 노드 5개, 간선 [(2,0,1),(3,1,2),(1,0,2),(4,2,3),(5,3,4)]의 MST 총비용을 손으로 예상한 뒤 코드로 확인해 보세요. (정답: 12)
3. 모든 노드가 연결될 수 없는 경우(간선이 부족한 경우) used가 n-1에 도달하지 못합니다. 함수 끝에서 used < n - 1이면 "연결 불가"를 알려주도록 고쳐 보세요. (힌트: return total if used == n - 1 else -1)