[백준] 1922 네트워크 연결 - 파이썬

최소 스패닝 트리 문제와 완전히 같은 문제다!

Union-Find 알고리즘과 Kruskal 알고리즘을 이용하여 해결했다.

Kruskal 알고리즘 이용
root를 저장하는 Nroot 배열을 생성한다. (여기서 root는 연결요소중 가장 작은 값, 처음에는 자기 자신을 저장)
간선들(Mlist)을 가중치 기준으로 정렬한다.
간선들이 이은 두 정점을 find함수를 통해 두 root(sRoot, eRoot)를 찾는다.
두 root가 다르다면 큰 root값을 작은 root값으로 만들어 연결되게 해준다.
가중치를 더한다.

import sys
input = sys.stdin.readline
 
N = int(input())
M = int(input())

Nroot = [i for i in range(N+1)]
Mlist = []

for _ in range(M):
    Mlist.append(list(map(int, input().split())))
 
Mlist.sort(key=lambda x: x[2]) # 크루스칼 알고리즘을 적용하기 위해 가중치 기준으로 정렬
 
 
def find(x):
    if x != Nroot[x]:
        Nroot[x] = find(Nroot[x])
    return Nroot[x]
 
 
answer = 0
for s, e, w in Mlist:
    sRoot = find(s)
    eRoot = find(e)
    if sRoot != eRoot:
        if sRoot > eRoot:
            Nroot[sRoot] = eRoot
        else:
            Nroot[eRoot] = sRoot
        answer += w
 
print(answer)