백준 1197 - 최소 스패닝 트리 (파이썬)

tree 배열에 입력을 받은 뒤 Kruskal’s algorithm을 사용했습니다.
Kruskal’s algorithm은 간선을 기준으로 오름차순 정렬을 한뒤 가중치가 낮은 간선부터 차례로 연결을 해주는 알고리즘입니다.

import sys

input = sys.stdin.readline

V, E = map(int, input().split())
tree = [list(map(int, input().split())) for _ in range(E)]
parent = [i for i in range(V + 1)]

tree.sort(key = lambda x : x[2])

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

def union(x, y, z):
    global answer
    x = find(x)
    y = find(y)
    if x != y:
        if x < y:
            parent[x] = y
        elif x > y:
            parent[y] = x
        answer += z

answer = 0
for s, e, w in tree:
    union(s, e, w)

print(answer)