[백준 1922] 네트워크 연결 (python)

1922번: 네트워크 연결

---

 

모든 컴퓨터를 연결해야하므로 Kruskal 알고리즘을 사용하자

 

1. arr에 간선들을 저장한뒤 비용을 기준으로 정렬을 한다.
2. 두 컴퓨터의 root를 찾은뒤 같지 않다면 비용을 더해주고 더 큰 root값의 root를 작은 root로 바꾸어준다.

 

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
arr = []
root = [i for i in range(N+1)]
for _ in range(M):
    s, e, v = map(int, input().split())
    arr.append([v, s, e])


def findRoot(x):
    if root[x] != x:
        root[x] = findRoot(root[x])
    return root[x]


result = 0
arr.sort()
for v, s, e in arr:
    sRoot = findRoot(s)
    eRoot = findRoot(e)
    if sRoot != eRoot:
        result += v
        if sRoot < eRoot:
            root[eRoot] = sRoot
        else:
            root[sRoot] = eRoot

print(result)