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

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

1647번: 도시 분할 계획

---

💡 문제 풀이

최소 신장 트리(MST) 문제이다.

 

크루스칼 알고리즘을 통해서 해결했다.

문제 자체는 알고리즘을 이해하고 있으면 어렵지 않으나, 도시를 분리해야 해야 하므로 마지막에 추가된 비용을 빼줘야 한다.

✔️ 느낀 점

솔직히 마지막에 왜 빼줘야 하는지 이해를 할 수 없다. 크루스칼 알고리즘 자체를 이해하는 것이 목표라서 그냥 이해하지 않고 넘어갔다.

💻 코드

import sys
input = sys.stdin.readline

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

def union(x,y):
    x = find(x)
    y = find(y)
    parent[y] = x

N, M = map(int, input().split())
parent = list(range(N+1))

edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a,b,c))
edges.sort(key=lambda x:x[2])

cost, lastChild = 0, 0

for v1, v2, c in edges:
    if find(v1) != find(v2):
        union(v1,v2)
        cost += c
        lastChild = c
        
print(cost - lastChild)