[백준16398] / 행성 연결 - 최소 스패닝 트리(MST)

 

백준16398

 

 

푼 날짜 : 2024.12.24

푼 문제 : [16398] / 행성 연결

사용한 언어 : python

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

 

 

접근방식 :

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

다만 평소에 리스트로 구현을 했기 때문에 행렬을 리스트로 변환하는 과정을 추가해주었다.

 

 

코드 :

import sys
import heapq

input = sys.stdin.readline

N = int(input())

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

# 행렬을 리스트로 변환하는 과정
for i in range(N):
    lst = list(map(int, input().split()))
    for j in range(len(lst)):
        if i != j:
            graph[i].append((j, lst[j]))


heap = [(0, 0)]
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))

print(sum_cost)

 

 

 

MST에 익숙해지는중 ~!