[문제]

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

[코드]

import sys
input = sys.stdin.readline

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

def union_parent(parent, x, y):
    a = find_parent(parent, x)
    b = find_parent(parent, y)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())
graph = []
for i in range(e):
    a, b, c = map(int, input().split())
    graph.append([c, a, b])
parent = [0] * (v + 1)
for i in range(1, v + 1):
    parent[i] = i

graph.sort()
result = 0
for i in graph:
    if find_parent(parent, i[1]) != find_parent(parent, i[2]):
        union_parent(parent, i[1], i[2])
        result += i[0]

print(result)

[풀이]

먼저 파라미터를 모두 입력 받는다

간선을 비용을 기준으로 오름차순으로 정렬한다

그리고 모든 간선에 대해서 a와 b의 부모가 같지 않다면 서로 연결되지 않은 것이므로 연견을 진행 해줄건데 비용으로 정렬을 했으니 간선이 추가되는 순서는 최소 비용부터이다

헷갈렸던 점은 union_parent에서 각 노드의 부모를 업데이트하는 것이 아니라 각 노드의 부모의 부모를 서로 연결함으로써 최상위 노드끼리 연결해야 한다는 개념!