[백준21924] / 도시 건설 - 최소 스패닝 트리(MST)

 

백준21924

 

 

푼 날짜 : 2024.12.25

푼 문제 : [21924] / 도시 건설

사용한 언어 : python

알고리즘 : 최소 스패닝 트리(MST)

 

 

 

접근방식 :

일반적인 MST 알고리즘을 사용했다.

절약 비용을 계산하기 위해 초기 비용을 계산하고 최소 연결 비용을 계산하여 절약 금액을 도출했다.

 

 

 

코드 :

import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())

graph = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]

# 초기 비용을 계산하기 위함
init_cost = 0

for _ in range(M):
    A, B, C = map(int, input().split())
    graph[A].append((B, C))
    graph[B].append((A, C))
    init_cost += C


heap = [(0, 1)]
sum_cost = 0

while heap:
    n_cost, n_edge = heapq.heappop(heap)

    if not visited[n_edge]:
        sum_cost += n_cost
        visited[n_edge] = 1

        for e, c in graph[n_edge]:
            if not visited[e]:
                heapq.heappush(heap, (c, e))

# 모두 잘 방문했다면 절약한 금액을 출력하고 아니라면 -1 출력을 위함
print(init_cost-sum_cost if sum(visited[1:]) == N else -1)

 

 

크리스마스에도 꾸준히 !