[크래프톤 정글] 백준 1197번 최소 스패닝 트리( Kruskal 알고리즘)

1197 번 문제는 MST(최소 스패닝 트리)를 구현하는 문제이다. MST를 구현하는 방법에서는 크루스칼 알고리즘,프림 알고리즘 두가지가 존재하는데 프림은 잘 사용 되지는 알고리즘이다. 따라서 이번 문제에서는 크루스칼을 이용해 풀어보자

크루스칼(Kruskal) 알고리즘은 가중치가 있는 연결 그래프에서 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘 중 하나다. 이 알고리즘은 그리디 알고리즘의 한 종류로, 간선의 가중치가 작은 것부터 차례대로 선택하여 MST를 구성하는 방법을 사용한다.

1. 기본 개념

• 그래프: 정점(Vertex)과 간선(Edge)으로 이루어진 구조.
• 신장 트리: 그래프의 모든 정점을 포함하며, 사이클이 없는 트리.
• 최소 신장 트리(MST): 그래프에서 모든 정점을 포함하며, 간선 가중치의 합이 최소가 되는 신장 트리.

2. 크루스칼 알고리즘의 주요 단계

크루스칼 알고리즘은 다음의 기본 단계를 통해 동작한다:

1. 간선 정렬:
   • 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.
2. 유니온-파인드(Union-Find) 자료구조 초기화:
   • 각 정점을 개별 집합으로 초기화한다.
   • 유니온-파인드 자료구조를 사용하여 간선 추가 시 사이클이 형성되는지 효율적으로 확인한다.
3. MST 구성:
   • 정렬된 간선 리스트에서 가중치가 작은 간선부터 하나씩 선택한다.
   • 선택한 간선이 사이클을 형성하지 않는다면 MST에 추가한다.
   • 이 과정을 간선의 수가 (정점 수 - 1)개가 될 때까지 반복한다.
4. MST 반환:
   • 최종적으로 선택된 간선들이 MST를 형성하며, 이 간선들의 가중치 합이 최소가 된다.

3. 유니온-파인드 자료구조

크루스칼 알고리즘에서 사이클 검사를 효율적으로 수행하기 위해 유니온-파인드 자료구조를 사용한다. 이 자료구조는 두 가지 주요 연산으로 구성된다:

1. Find:
   • 특정 정점이 속한 집합의 대표(루트) 정점을 찾는다.
   • 경로 압축(Path Compression)을 통해 트리의 높이를 줄여 이후의 연산을 빠르게 수행할 수 있다.
2. Union:
   • 두 개의 집합을 하나로 합친다.
   • 랭크(Rank)를 기준으로 트리의 균형을 유지하며, 트리의 높이가 낮은 트리를 높이가 높은 트리 아래에 병합한다.

유니온-파인드 자료구조의 구현:

class UnionFind:
    def __init__(self, n):
        # 각 정점의 부모를 가리키는 배열을 초기화
        # 처음에는 모든 정점이 자기 자신을 부모로 가리킴
        self.parent = list(range(n))

        # 각 정점의 랭크(트리의 깊이)를 나타내는 배열 초기화
        # 초기에는 모든 트리의 높이가 1이므로 rank[i] = 1
        self.rank = [1] * n

    def find(self, u):
        # u가 자기 자신을 부모로 가지지 않는다면, 루트 노드를 찾을 때까지 부모를 따라감
        if u != self.parent[u]:
            # 경로 압축: u의 부모를 재귀적으로 루트 노드로 설정
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        # u와 v의 루트 노드를 각각 찾음
        root_u = self.find(u)
        root_v = self.find(v)

        # 두 루트 노드가 다르다면, 즉, u와 v가 서로 다른 집합에 속해 있다면,
        # 두 집합을 합침
        if root_u != root_v:
            # u의 트리 높이가 v의 트리 높이보다 크다면, v의 부모를 u로 설정
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            # 반대로 v의 트리 높이가 더 크다면, u의 부모를 v로 설정
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            # 두 트리의 높이가 같다면, 한쪽을 다른 쪽 아래로 병합하고 병합 후 랭크를 증가시킴
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

4. 크루스칼 알고리즘 구현 예시

def kruskal(V, edges):
    uf = UnionFind(V)
    edges.sort(key=lambda x: x[2])#w(가중치) 를 기준으로 edges 를 오름차순 정렬
    mst_weight = 0 # 총 가중치 초기화
    mst_edges = 0 # 총 간선 초기화

    for u, v, weight in edges:
        u -= 1  # 1-indexed에서 0-indexed로 맞추기 위해
        v -= 1  # 1-indexed에서 0-indexed로 맞추기 위해
        if uf.find(u) != uf.find(v): # u와 v 가 같은 그룹 인지 확인 , 만약 서로 다른 그룹 이라면
            uf.union(u, v) # 서로 같은 그룹으로 합친다.
            mst_weight += weight #mst 의 총 가중치에 누적 합계
            mst_edges += 1 #mst에 포함 된 간선의 개수 누적 합계
            if mst_edges == V - 1: # mst의 간선의 개수가 v(노드의 수) 와 동일한지 확인하여 mst가 완성되었는지 확인
                break # 완성 되었으면 탈출

    return mst_weight

5. 크루스칼 알고리즘의 시간 복잡도

• 간선 정렬: O(E log E) (간선의 수 E)
• 유니온-파인드 연산: O(E log V) (정점의 수 V)
• 전체 시간 복잡도: O(E log E)로, 이는 O(E log V)로 표현될 수 있다.

6 크루스칼 알고리즘의 특성

• 적용 가능성: 모든 간선의 가중치가 같을 수 있는 경우에도 동작하며, 가중치가 음수일 때도 문제없이 작동한다.
• 장점: 간선의 수가 정점의 수에 비해 적은 경우 유리하며, 구현이 간단하다.
• 단점: 간선의 수가 많고, 정렬 시간이 큰 경우 프림 알고리즘(Prim's algorithm)이 더 효율적일 수 있다.

7. 예제 문제

주어진 그래프:

• 정점: 4개 (A, B, C, D)
• 간선:
  • A - B: 1
  • B - C: 3
  • C - D: 4
  • A - C: 2
  • B - D: 5

크루스칼 알고리즘 적용:

1. 간선 정렬:
   • A - B: 1
   • A - C: 2
   • B - C: 3
   • C - D: 4
   • B - D: 5
2. MST 구성:
   • A - B (1) 추가
   • A - C (2) 추가
   • C - D (4) 추가

결과:

• MST: A - B, A - C, C - D
• MST 가중치: 7