[BOJ] 최소 스패닝 트리

---

코드

import sys
input = sys.stdin.readline

# INPUT
V, E = map(int, input().split())
edges = []
for _ in range(E):
    A, B, C = map(int, input().split())
    edges.append((A, B, C))
edges.sort(key=lambda x:x[2])    # 비용이 작은 순서대로 정렬

# union-find
parent = [i for i in range(V+1)]
def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x])
    return parent[x]

def union_parent(a, b):    # union 연산
    a = get_parent(a)
    b = get_parent(b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def is_same_parent(a, b):    # 사이클 여부 확인
    return get_parent(a) == get_parent(b)

# 크루스칼 알고리즘
ans = 0
for e in edges:
    a, b, cost = e
    if not is_same_parent(a, b):    # 간선 연결 시 사이클이 만들어지지 않는다면
        union_parent(a, b)    # 연결하고 비용 추가
        ans += cost

print(ans)

결과

풀이 방법

• 최소 스패닝 트리(MST)의 가중치를 구하는 2가지 알고리즘 중 하나인 크루스칼 알고리즘을 구현하였다. 다른 하나는 프림 알고리즘이 있다.
• 최소 스패닝 트리는 트리의 모든 정점을 연결하는 부분 트리(스패닝 트리) 중 간선들의 가중치 합이 최소인 것을 말한다.
• 크루스칼 알고리즘은, 가중치(비용)가 작은 순서대로 간선을 선택(연결)하되 사이클을 만드는 간선을 제외하면 된다.
• 간선 중심으로 계산하기 때문에 간선이 적은 경우에는 크루스칼이 유용하고, 정점 중심으로 계산하는 프림 알고리즘은 정점이 적은 경우 유용하다고 한다.
• 간선을 연결하면서 사이클 여부를 확인하는 데에 Union-Find 알고리즘이 적용된다. 간선으로 연결하려는 두 정점의 부모가 같으면 사이클이 형성된다고 판단한다.

---