[ 백준 / 골드4 / 파이썬 Python ] 1647번 - 도시 분활 계획

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

1647번: 도시 분할 계획

 

코드

---

import sys
input = sys.stdin.readline

def ancestor(node):
    if parent[node] != node:
        parent[node] = ancestor(parent[node])
    return parent[node]

n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(m)]
parent = [x for x in range(n+1)]
maxv = 0
s = 0
for a,b,c in sorted(graph, key=lambda x: x[2]):
    pa, pb = ancestor(a),ancestor(b)
    if pa != pb:
        s += c
        maxv = max(maxv,c)
        if pa > pb:
            parent[pa] = b
        else:
            parent[pb] = a

print(s-maxv)

 

풀이

---

문제에는 두 개의 도시로 나누고 모든 도시는 연결되어 있다고 조금 복잡하게 적혀있지만 결국은 단순한 최소 스패닝 트리 문제이다.

모두 연결되어 있는 한 도시를 두 개로 나누고, 나뉜 두 도시는 서로끼리만 모두 연결되어 있다. 그 말은 두 개의 최소 스패닝 트리를 구하라는 의미로 들릴 수 있지만 그저 한 개의 스패닝 트리를 구하고 그 중 가장 큰 가중치를 가진 간선을 없애면 된다.

 

기존의 최소 스패닝 트리 문제처럼 가중치를 기준으로 오름차순 정렬하여 스패닝 트리를 만들어간다. 트리에 노드가 추가될 때마다 가중치를 모두 더하고 그 중 가장 큰 값을 저장한다. 마지막에 최종 가중치에서 가장 큰 가중치만 빼주면 답이 된다.