[Algorithm] Kruskal 알고리즘

Kruskal Algorithm 이란?

• 가중치가 작은 간선부터 선택하면서, 사이클이 생기지 않도록 추가하는 방식
• 알고리즘 과정

1. 모든 간선을 가중치 기준으로 오름차순 정렬한다.
2. 가중치가 가장 작은 간선부터 하나씩 선택한다.
3. 유니온-파인드를 사용해 사이클이 생기는지 확인한다.
   • 만약 사이클이 생기지 않는다면, 해당 간선을 선택한다.
   • 만약 사이클이 생긴다면, 해당 간선을 버린다.
4. N-1개의 간선이 선택될 때까지 반복한다. (MST의 성질)

import sys
input = sys.stdin.readline

# 유니온 파인드 (경로 압축 적용)
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)
    
    if rootA < rootB:
        parent[rootB] = rootA
    else:
        parent[rootA] = rootB

def kruskal():
    V, E = map(int, input().split())  # 노드 개수, 간선 개수
    edges = []
    parent = [i for i in range(V + 1)]  # 유니온 파인드용 부모 배열

    # 간선 정보 입력받기
    for _ in range(E):
        a, b, cost = map(int, input().split())
        edges.append((cost, a, b))  # (가중치, 노드1, 노드2) 순으로 저장

    edges.sort()  # 가중치 기준으로 정렬
    mst_weight = 0
    mst_edges = 0

    # 크루스칼 알고리즘 실행
    for cost, a, b in edges:
        if find(parent, a) != find(parent, b):  # 사이클이 아니라면 선택
            union(parent, a, b)
            mst_weight += cost
            mst_edges += 1
            if mst_edges == V - 1:  # MST가 완성되었으면 종료
                break

    print(mst_weight)  # 최소 비용 출력

kruskal()