[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1647번 _ 도시 분할 계획

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

1647번: 도시 분할 계획

[문제]

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

 

[입력]

첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다.

[출력]

첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다.

 

[아이디어]

1) 유지 비용을 최소로하면서 모든 집을 연결한다. (최소 스패닝 트리)

2) 이때 연결에 사용하는 길 중 비용이 가장 큰 것을 업데이트하며 보관한다.

3) 모든 집이 연결되면 2)의 최대 비용의 길을 삭제하여 마을을 둘로 분리한다.

 

# import sys
# input = sys.stdin.readline

n,m = map(int,input().split())
d = list(range(n+1))
dst = []
for _ in range(m):
    a,b,c = map(int,input().split())
    dst.append((a,b,c))   

def root(x):
    if d[x]==x:
        return x
    d[x] = root(d[x])
    return d[x]
    
def union(x,y):
    a = root(x); b = root(y) 
    if a==b:
        return
    d[b] = a

dst.sort(key = lambda x:x[2], reverse=True)
max_ = 0; ans = 0; cnt = 0
while cnt<n and dst:
    i,j,cost = dst.pop()
    if root(i)!=root(j):
        ans += cost
        cnt +=1
        max_=max(max_, cost)
        union(i,j)

print(ans - max_)