7-4. 그리디: 최소 스패닝 트리 (Kruskal)

1. 최소 신장 트리 (MST)의 재조명

최소 신장 트리 (Minimum Spanning Tree, MST)는 그래프 이론에서 매우 중요한 개념입니다. 연결된 가중치 그래프 내의 모든 정점을 연결하면서, 간선 가중치의 합을 최소화하는 부분 트리입니다. 쉽게 말해, 모든 도시를 연결하는 도로망을 건설하되, 도로 건설 비용을 최소화하는 방법을 찾는 문제입니다.

MST는 네트워크 설계, 클러스터링, 이미지 분할 등 다양한 실용적인 문제에 적용됩니다. 예를 들어, 통신 네트워크를 구축할 때 모든 도시를 연결하면서 케이블 설치 비용을 최소화하거나, 물류 시스템에서 모든 창고를 연결하는 데 필요한 최소한의 도로를 설계하는 데 활용될 수 있습니다.

MST를 찾는 알고리즘에는 대표적으로 Prim 알고리즘과 Kruskal 알고리즘이 있습니다. 이전 포스트에서 Prim 알고리즘에 대해 다루었으니, 이번에는 Kruskal 알고리즘에 대해 자세히 살펴보겠습니다. 두 알고리즘 모두 그리디 (Greedy) 알고리즘을 기반으로 하며, 각기 다른 방식으로 MST를 구성합니다.

2. Kruskal 알고리즘: 탐욕적인 접근

Kruskal 알고리즘은 그리디 패러다임을 사용하여 MST를 찾습니다. 즉, 각 단계에서 현재 상황에서 최적이라고 여겨지는 선택을 합니다. 구체적으로는, 가중치가 가장 작은 간선부터 차례대로 선택하면서 사이클을 형성하지 않는 간선들을 MST에 추가합니다.

1) 알고리즘 단계

Kruskal 알고리즘은 다음과 같은 단계로 진행됩니다.

1. 간선 정렬: 그래프의 모든 간선을 가중치 오름차순으로 정렬합니다.
2. 간선 선택: 정렬된 간선들을 순회하면서, 현재 간선이 MST에 추가될 수 있는지 확인합니다.
3. 사이클 검사: 선택된 간선이 MST에 추가될 경우 사이클을 형성하는지 확인합니다. 사이클을 형성하지 않는 경우에만 MST에 추가합니다.
4. 반복: 모든 정점이 연결될 때까지 2, 3단계를 반복합니다.

2) 사이클 탐지: Union-Find 자료구조

Kruskal 알고리즘의 핵심은 사이클을 효율적으로 탐지하는 것입니다. 이 과정에서 Union-Find 자료구조가 유용하게 사용됩니다. Union-Find는 다음과 같은 두 가지 주요 연산을 지원합니다.

• Find(v): 정점 v가 속한 집합의 대표 노드를 반환합니다.
• Union(u, v): 정점 u와 v가 속한 집합을 합칩니다.

사이클을 탐지하기 위해, 간선을 선택할 때 해당 간선의 두 정점(u, v)이 같은 집합에 속하는지 확인합니다. 만약 Find(u)와 Find(v)의 결과가 같다면, u와 v는 이미 같은 집합에 속해 있으므로, 해당 간선을 추가하면 사이클이 발생합니다. 그렇지 않다면, u와 v를 연결하고, Union(u, v) 연산을 수행합니다.

3. Kruskal 알고리즘의 동작 예시

다음은 Kruskal 알고리즘의 동작 예시입니다.

예시 그래프:

1) 간선 정렬

간선들을 가중치 오름차순으로 정렬합니다.

2) 간선 선택 및 Union-Find 적용

• E - F (가중치 1): E와 F는 서로 다른 집합에 속하므로, MST에 추가하고 Union(E, F) 연산을 수행합니다.
• F - G (가중치 2): F와 G는 서로 다른 집합에 속하므로, MST에 추가하고 Union(F, G) 연산을 수행합니다.
• A - B (가중치 4): A와 B는 서로 다른 집합에 속하므로, MST에 추가하고 Union(A, B) 연산을 수행합니다.
• C - F (가중치 7): C와 F는 서로 다른 집합에 속하므로, MST에 추가하고 Union(C, F) 연산을 수행합니다.
• D - E (가중치 7): D와 E는 서로 다른 집합에 속하므로, MST에 추가하고 Union(D, E) 연산을 수행합니다.
• A - C (가중치 8): A와 C는 서로 다른 집합에 속하지만, MST에 추가 시 사이클이 발생하므로 추가하지 않습니다.
• B - D (가중치 8): B와 D는 서로 다른 집합에 속하지만, MST에 추가 시 사이클이 발생하므로 추가하지 않습니다.
• B - E (가중치 9): B와 E는 서로 다른 집합에 속하지만, MST에 추가 시 사이클이 발생하므로 추가하지 않습니다.
• E - G (가중치 10): E와 G는 서로 다른 집합에 속하지만, MST에 추가 시 사이클이 발생하므로 추가하지 않습니다.
• B - C (가중치 11): B와 C는 서로 다른 집합에 속하지만, MST에 추가 시 사이클이 발생하므로 추가하지 않습니다.

3) 결과

선택된 간선: E-F, F-G, A-B, C-F, D-E

MST의 총 가중치: 1 + 2 + 4 + 7 + 7 = 21

4. Kruskal 알고리즘의 구현 (Python)

다음은 Python으로 구현된 Kruskal 알고리즘의 예시입니다.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])  # 경로 압축 (Path Compression)
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j
            return True  # Union 성공
        return False  # 이미 같은 집합에 속함

def kruskal(graph):
    """
    Kruskal 알고리즘을 사용하여 최소 신장 트리를 찾습니다.

    Args:
        graph: 간선 정보를 담은 리스트. 각 간선은 (u, v, weight) 형태의 튜플입니다.
               u, v는 정점의 인덱스, weight는 가중치입니다.

    Returns:
        MST를 구성하는 간선의 리스트, MST의 총 가중치.
    """
    # 1. 간선 정렬
    edges = sorted(graph, key=lambda x: x[2])  # 가중치 기준으로 정렬
    num_vertices = len({v for edge in graph for v in edge[:2]})  # 정점의 개수 (0부터 시작)

    # 2. Union-Find 초기화
    uf = UnionFind(num_vertices)
    mst = []
    total_weight = 0

    # 3. 간선 선택 및 사이클 검사
    for u, v, weight in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight

    return mst, total_weight

# 예시 그래프
graph = [
    (0, 1, 4),  # A-B
    (0, 2, 8),  # A-C
    (1, 2, 11), # B-C
    (1, 3, 8),  # B-D
    (1, 4, 9),  # B-E
    (2, 5, 7),  # C-F
    (3, 4, 7),  # D-E
    (4, 5, 1),  # E-F
    (4, 6, 10), # E-G
    (5, 6, 2)   # F-G
]

mst, total_weight = kruskal(graph)
print("MST:", mst)
print("Total weight:", total_weight)

위 코드에서 UnionFind 클래스는 find와 union 연산을 구현합니다. find 연산에서 경로 압축(path compression)을 사용하여 성능을 최적화합니다. kruskal 함수는 입력 그래프를 받아 Kruskal 알고리즘을 수행하고, MST를 구성하는 간선과 총 가중치를 반환합니다.

5. 시간 복잡도 분석

Kruskal 알고리즘의 시간 복잡도는 다음과 같습니다.

• 간선 정렬: $O(E \log E)$ ($E$는 간선의 개수)
• Union-Find 연산: $O(E \alpha(V))$ ($V$는 정점의 개수, $\alpha$는 아커만 함수의 역함수. 거의 상수 시간에 가깝습니다.)

따라서, Kruskal 알고리즘의 전체 시간 복잡도는 $O(E \log E)$입니다. 그래프가 밀집된 경우 ($E$가 $V^2$에 가까운 경우), 시간 복잡도는 $O(V^2 \log V)$가 됩니다.

6. Kruskal 알고리즘의 장단점

1) 장점

• 구현의 용이성: Prim 알고리즘에 비해 구현이 간단합니다.
• 유연성: 그래프의 형태에 크게 영향을 받지 않습니다. (희소 그래프에 적합)

2) 단점

• 간선 정렬: 간선 정렬 단계가 필요하므로, 그래프의 크기가 커질수록 성능 저하가 발생할 수 있습니다.
• Union-Find 자료구조: Union-Find 자료구조를 사용해야 하므로, 추가적인 메모리 공간이 필요합니다.

7. Prim vs. Kruskal: 선택의 갈림길

Prim 알고리즘과 Kruskal 알고리즘은 모두 MST를 찾는 데 사용되지만, 몇 가지 차이점이 있습니다.

• 선택 방식: Prim 알고리즘은 시작 정점에서 가장 가까운 정점을 점진적으로 확장하는 방식으로 MST를 구성합니다. Kruskal 알고리즘은 간선을 가중치 순으로 선택하여 MST를 구성합니다.
• 구현: Kruskal 알고리즘은 Prim 알고리즘보다 구현이 간단합니다.
• 시간 복잡도: 일반적으로 Prim 알고리즘은 밀집 그래프에서, Kruskal 알고리즘은 희소 그래프에서 더 효율적입니다. 하지만, 두 알고리즘 모두 $O(E \log E)$ 시간 복잡도를 가지므로, 그래프의 크기에 따라 성능 차이가 크게 나타나지는 않습니다.

어떤 알고리즘을 선택할지는 문제의 특성과 구현의 편의성을 고려하여 결정해야 합니다.

8. 실전에서의 활용

Kruskal 알고리즘은 다음과 같은 다양한 문제에서 활용될 수 있습니다.

• 네트워크 연결 비용 최소화: 여러 도시를 연결하는 통신망 구축 비용을 최소화하는 문제
• 도로 건설 비용 최소화: 여러 도시를 연결하는 도로 건설 비용을 최소화하는 문제
• 클러스터링: 데이터 포인트들을 연결하여 클러스터를 형성하고, 클러스터 간의 연결 비용을 최소화하는 문제

• 크루스칼 알고리즘을 활용한 코딩 테스트 문제 풀이:

  • 백준 1197번: 최소 스패닝 트리: 기본적인 MST 문제. 주어진 그래프에 Kruskal 알고리즘을 적용하여 최소 신장 트리의 가중치를 구하는 문제입니다.
  • 프로그래머스: 섬 연결하기: 섬들을 연결하는 최소 비용을 구하는 문제입니다. Kruskal 알고리즘을 사용하여 각 섬을 연결하는 최소 비용을 계산할 수 있습니다.
  • 백준 1922번: 네트워크 연결: 컴퓨터들을 연결하는 네트워크를 구축하는데 필요한 최소 비용을 구하는 문제입니다. Kruskal 알고리즘을 활용하여 해결할 수 있습니다.

이러한 문제들을 통해 Kruskal 알고리즘의 실전 적용 능력을 향상시킬 수 있습니다.

9. 결론

Kruskal 알고리즘은 그리디 알고리즘을 사용하여 MST를 효율적으로 찾는 강력한 도구입니다. 사이클을 탐지하기 위한 Union-Find 자료구조의 활용은 알고리즘의 핵심적인 부분이며, 구현의 용이성과 유연성으로 인해 다양한 문제에 적용될 수 있습니다. Prim 알고리즘과의 비교를 통해 각 알고리즘의 장단점을 파악하고, 문제의 특성에 맞는 알고리즘을 선택하는 것이 중요합니다.