백준 1197 최소 스패닝 트리

문제 링크

크루스칼과 union-find를 이용해 트리를 만드는 문제
간선 정보를 입력받은 후 가중치를 기준으로 정렬했다.
이후 union-find를 이용해 공통 조상으로 묶어주며, 묶을 때마다 가중치를 더해주고 완료 후 해당 값을 반환했다.

import sys
input=lambda:sys.stdin.readline().rstrip()

def find(n):
    if n != node[n]:
        node[n] = find(node[n])
        #시간 줄이기
        return node[n]
    return n

def union(a, b):
    parent = find(a)
    child = find(b)
    if parent>child: parent, child = child, parent # 간선을 이을 때는 인덱스 값 낮은 쪽이 부모.
    if parent != child:
        node[child] = parent
        return True
    return False # 부모가 같을 경우, 거짓 반환.

v, e = map(int, input().split())

node = list(range(v+1))
weight = [tuple(map(int, input().split())) for _ in range(e)]
weight.sort(key=lambda x:x[2])

answer = 0 # 출력(트리의 가중치)
for i in weight:
    if union(i[0], i[1]):
        answer += i[2]
print(answer)