[백준] 1197번 : 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

해당 문제는 Union, Find 문제로 최소 신장 트리를 구하는 문제이다. 간선의 개수를 입력받고, 간선을 짧은순으로 정렬한뒤 순서대로 정점을 Union 하는데, 사이클이 생기지 않게 Find로 부모를 확인한뒤 Union 하면된다.

V, E = map(int, input().split())
parent = [v1 for v1 in range(V+1)] # 정점의 개수만큼 생성

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

def union(a, b):
    a = find(a)
    b = find(b)

    # 작은 루트 노드를 기준으로 합침
    if b < a:
        parent[a] = b
    else:
        parent[b] = a
        
graph = []
for _ in range(E): # 간선의 개수
    a, b ,c = map(int, input().split())
    graph.append([c, a, b])

graph.sort()

result = 0
for cost, a , b in graph:
    if find(a) != find(b):
        union(a, b)
        result += cost

print(result)