[백준/Python] 1647번 도시 분활 계획

문제

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

풀이

import heapq
import sys
input = sys.stdin.readline
def prim(graph, start):
    mst = []  
    visited = set() 
    min_heap = [(0, start, None)] 
    
    total_weight = 0  
    
    while min_heap:
        weight, current, previous = heapq.heappop(min_heap)  
        
        if current in visited:
            continue  
        
        visited.add(current)
        total_weight += weight
        
        if previous is not None:
            mst.append((previous, current, weight))

        for neighbor, edge_weight in graph[current]:
            if neighbor not in visited:
                heapq.heappush(min_heap, (edge_weight, neighbor, current))
    
    return mst, total_weight

n, m = map(int, input().split())
graph = [[] for i in range(n + 1)]

for i in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
    temp = a
    
mst, answer = prim(graph=graph, start=temp)
mst.sort(key=lambda a: -a[2])
long = mst[0][2]
# print(mst)
print(answer-long)

 

pypy로 제출해야 풀립니다.. 아마도 

 

Prim알고리즘을 이용한 풀이입니다. 

두 도시로 분할할 계획이기에 mst를 구한뒤 가장 큰 간선을 제거해주면 가장 작은 mst 2개가 완성됩니다.