[BOJ/백준] 21924 도시건설

import heapq
import sys

input = sys.stdin.readline
N,M = map(int,input().split())


graph = [{} for _ in range(N+1)]
total_pay = 0
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay
    total_pay += pay

INF = float('inf')

distance = [INF for _ in range(N+1)]
visited = [False for _ in range(N+1)]
node_list = []
heapq.heappush(node_list,(0,1))
result = 0
distance[1] = 0
cnt = 0
while node_list:
    dis,node = heapq.heappop(node_list)

    if visited[node]:
        continue
    result += dis
    cnt += 1
    visited[node] = True
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            distance[next_node] = graph[node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))


if cnt == N:
    print(total_pay-result)
else:
    print(-1)

 

이 문제는 전형적인 MST 문제였다.

 

그래서 나는 MST에서 익숙한 프림알고리즘을 이용해, 돌렸으며, 방문한 전체 노드의 수를 세주었다.

 

만약 전체 노드의 개수가 일치 하지 않으면, 모든 노드들을 연결 할 수 없으므로, -1을 출력해주었고,

 

전체 노드의 개수가 같으면, 원래 전체 비용에서 MST했을때의 비용을 빼주어서, 절약한 값을 출력해주었다.