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

해당 글은 백준 1647번 '도시 분할 계획' 문제를 다룬다.

문제

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

1647번: 도시 분할 계획

 

설명

해당 문제는 크루스칼 알고리즘으로 해결할 수 있다.

분리된 두 마을을 만들고, 그 사이에 길은 없애야 한다. 여기서 분리된 마을안에는 최소 1개의 집만 존재해도 되므로 크루스칼 최소신장 트리를 만들고, 마지막 길만 없애주면 분리된 두 마을을 만드는 최소길이 값이 나온다.

 

코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

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

graph = []
for _ in range(m):
    a, b, c = map(int, input().split())
    graph.append((c, a, b))

graph.sort()

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

def union_parent(parent, x, y):
    a = find_parent(parent, x)
    b = find_parent(parent, y)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

result = 0
last = 0
for edge in graph:
    c, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += c
        last = c

print(result-last)