크루스칼 알고리즘 :: 백준 1197 파이썬

최소 스패닝 트리(Minimum Spanning Tree, MST)를 찾는 문제는 크루스칼(Kruskal) 알고리즘이나 프림(Prim) 알고리즘을 사용하여 해결할 수 있습니다. 크루스칼 알고리즘과 다익스트라 알고리즘 모두 그래프의 모든 정점들을 연결하는 최소 비용의 트리를 찾는 데 사용됩니다.

크루스칼 알고리즘은 간선을 가중치에 따라 정렬하고, 가장 작은 간선부터 시작하여 사이클을 만들지 않는 한 트리에 추가하는 방식으로 동작합니다.

1. 모든 간선을 가중치 순으로 정렬합니다.
2. 각 간선을 순서대로 확인하면서, 해당 간선을 추가해도 사이클이 생기지 않으면 트리에 추가합니다.
3. 사이클이 생기지 않는다는 것을 확인하기 위해서 Union-Find 자료구조를 사용합니다.

*Union-Find 자료구조는 서로소 집합(Disjoint Set) 자료구조로, 여러 개의 원소가 있을 때 이들을 몇 개의 그룹으로 나누고, 그룹 간의 합치기와 특정 원소가 어느 그룹에 속하는지 찾는 연산을 효율적으로 처리하는 데 사용됩니다. 

1. Find: 특정 원소가 어느 그룹에 속하는지 찾는 연산.
2. Union: 두 그룹을 하나로 합치는 연산.

 

1197번))

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

def union(parent, rank, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    
    if rootX != rootY:
        if rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        elif rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        else:
            parent[rootY] = rootX
            rank[rootX] += 1

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])  # 가중치 기준으로 정렬
    parent = list(range(n + 1))
    rank = [0] * (n + 1)
    mst_weight = 0
    mst_edges = 0
    
    for u, v, weight in edges:
        if find(parent, u) != find(parent, v):
            union(parent, rank, u, v)
            mst_weight += weight
            mst_edges += 1
            if mst_edges == n - 1:  # MST 완성
                break

    return mst_weight

# 입력 처리
import sys
input = sys.stdin.read
data = input().split()

V = int(data[0])
E = int(data[1])
edges = []

index = 2
for _ in range(E):
    A = int(data[index])
    B = int(data[index + 1])
    C = int(data[index + 2])
    edges.append((A, B, C))
    index += 3

result = kruskal(V, edges)
print(result)