크루스칼과 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)