[Python] 백준 1647번 - 도시 분할 계획

문제 https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

크루스칼 사랑해.

이제 크루스칼은 문제 이해만 잘 하면 나름 수월하게 풀 수 있다.

근데 그 문제 이해가 오래 걸린다..

이걸 어떻게 크루스칼로 풀어야 하는지, 이게 왜 크루스칼인지.. 뭐 풀다보면 익숙해지겠지..?

 

 

import sys
input = sys.stdin.readline

def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])
    return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a

n, m = map(int, input().split())
edge = []
parent = [i for i in range(n+1)]
ans = 0

for i in range(m):
    a, b, c = map(int, input().split())
    edge.append((a, b, c)) #c: 가중치

edge.sort(key=lambda x:x[2])

for i in range(1, n+1):
    parent[i] = i

for i in edge:
    a, b, c = i
    if find(a) != find(b):
        union(a, b)
        ans += c
        last = c
print(ans - last)