[백준 1647] 도시 분할 계획(Python)

1. 아이디어

하나의 마을에서 최소 유지비 합을 갖는 길들을 찾는다.(MST를 이용하여 찾는다.) 그리고 그 길들 중 비용이 가장 큰 길을 제거하고 나머지 길들의 유지비 합을 구하면 된다.

2. 코드

import sys

v, e = map(int, sys.stdin.readline().rsplit())
uf = [-1 for _ in range(v+1)]

def find(a):
    if uf[a] < 0: return a
    uf[a] = find(uf[a])
    return uf[a]

def merge(a, b):
    a = find(a)
    b = find(b)
    if a == b: return False
    uf[b] = a
    return True

edges = []
for _ in range(e):
    a, b, w = map(int, sys.stdin.readline().rsplit())
    edges.append((w, a, b))

edges.sort()
total, cnt, max_cost = 0, 0, 0
for w, a, b in edges:
    if merge(a, b):
        total += w
        cnt += 1
        max_cost = max(max_cost, w)
        if cnt == v-1: break

print(total-max_cost)