[백준 1647번] 파이썬 - 도시 분할 계획

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

1647번: 도시 분할 계획

 

 

# 조건

• 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다.
• 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.
• 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다.
• 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다.
• 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.
• 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다.
• 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다.
• 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다.
• 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
• 그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다.
• 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다.
• 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.
• 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

 

# 접근 방법

• 최소 신장 트리 (최소 스패닝 트리)문제이다.
• 두 마을로 분리하기 위해 먼저 최소 신장 트리를 구현하고, 구성 간선 중 비용이 가장 높은 간선을 제거하면 된다.
• Prim알고리즘 또는 Kruskal 알고리즘 사용하면 된다.

 

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
def find_set(x):  
    if x == parent[x]:  
        return x  
    parent[x] = find_set(parent[x])  
    return parent[x]  
  
def union(x, y):  
    x = find_set(x)  
    y = find_set(y)  
    if x < y:  
        parent[y] = x  
    else:  
        parent[x] = y  
  
  
N, M = map(int, input().split())  
route = [[*map(int, input().split())] for _ in range(M)]  
# 비용 기준 오름 차순 정렬  
route.sort(key=lambda x:x[2])  
  
# 부모 노드 기록 리스트  
parent = [i for i in range(N+1)]  
# MST의 간선 수 = 노드수 -1V = N-1  
# 선택한 edge 수  
edge = 0  
# MST 가중치의 합  
total = 0  
# 선택 간선 넣어줄 리스트  
select = []  
for a, b, c in route:  
	# 부모 노드를 체크해준다.
    if find_set(a) != find_set(b):
	    # 방문하지 않은 곳이라면 방문 노드수 +=1
	    # 부모 노드값 갱신  
        edge+=1  
        union(b, a)  
        total += c  
        select.append(c)  
        if edge == N-1:  
            break  
# 마을 분리 위해 마지막 간선 제거  
total -= select.pop()  
  
print(total)