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

이 문제를 풀려고 하는 방향은 맞았으나, 크루스칼 알고리즘을 몰라서 못풀었다. 구글링을 통해 해결을 했는데 아직 익숙하지는 않다.

import sys
from collections import deque
import copy
 
def union(x,y):
    x = find(x)
    y = find(y)
 
    if x<y:
        parent[y] = x
    else:
        parent[x] = y
 
 
def find(x):
    if x!= parent[x]:
        parent[x] = find(parent[x])
    return parent[x]
 
 
n = int(input())
m = int(input())
 
k = []
for i in range(m):
 
    a,b,c = map(int,input().split())
    k.append((c,a,b))
 
k.sort(reverse = True)
 
parent = [i for i in range(n+1)]
 
 
r,cnt = 0,0
while cnt != n-1:
    w,a,b = k.pop()
    if find(a) == find(b):
        continue
 
    union(a,b)
    r += w
    cnt += 1
 
print(r)