백준 1647 도시 분할 계획

문제

도시 분할 계획

도시를 둘로 나눠 최소 유지 비용을 구하자

난이도 : Gold4

---

풀이

1. kruskal 알고리즘을 이용해 mst를 만든다.
2. mst를 둘로 나누는데, 가장 cost가 큰 길을 없애면 최소 비용을 구할 수 있다. 따라서 전체 cost에서 각 cost들 중 가장 큰 cost를 빼서 최소 비용을 구한다.

---

코드

import sys

n, m = list(map(int, sys.stdin.readline().split()))
data = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]

parent = [0] * (n+1)
for i in range(1, n+1):
    parent[i] = i
edges = sorted(data, key=lambda x:x[-1])  # 맨 마지막 정보가 cost이므로 마지막 원소를 기준으로 sort

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

def union(a, b, parent):
    x = find(a, parent)
    y = find(b, parent)
    
    if x < y:
        parent[y] = x
    else:
        parent[x] = y
        
def kruskal():
    total = 0
    costs = []  # 마을을 두 개로 분할한다. 즉 mst 생성하면서 모든 cost를 저장한 뒤 가장 비용이 큰 마을만 따로 뽑아내서 두 개로 분할하면 전체 비용 최소
    for i in range(m):
        a, b, cost = edges[i]
        if find(a, parent) != find(b, parent):
            union(a, b, parent)
            total += cost
            costs.append(cost) 
            
    print(total - max(costs))
    
kruskal()

        

---

결과

도시를 둘로 나눌 때 가장 큰 cost의 길을 없애는 아이디어를 떠올리는게 쉽지 않았다.