[백준1922] / 네트워크 연결 - 최소 스패닝 트리(MST)

 

백준1922

 

 

푼 날짜 : 2024.12.22

푼 문제 : [1922] / 네트워크 연결

사용한 언어 : python

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

 

 

접근방식 :

전형적인 MST 알고리즘으로 풀이했다.

파이썬의 heapq를 사용하면 자동으로 최소 힙 형태로 정렬이 되기 때문에 해당 모듈을 사용하여 구현했다.

 

 

 

코드 :

import sys
import heapq

input = sys.stdin.readline

N = int(input())
M = int(input())

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

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((c, b))
    graph[b].append((c, a))

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

while heap:
    # 최소 힙이기 때문에 가장 작은 값부터 꺼낼 수 있다.
    n_cost, n_edge = heapq.heappop(heap)
    # 방문하지 않은 노드일때
    if not visited[n_edge]:
    	# 값 누적
        min_cost += n_cost
        # 방문처리
        visited[n_edge] = 1

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

print(min_cost)

 

 

파이썬으로 알고리즘을 풀이하며 heapq를 자주 사용하게 되는데

heap 자료구조에 대해서도 한 번 포스팅 해보면 좋을 것 같다. (메모메모..)