행성 연결 (백준 16398)

   MST 풀이 방법 중에서 Prim 알고리즘을 사용했다. 크루스칼 알고리즘은 Union find를 해야 해서 프림 알고리즘에 비해 좀 더 복잡하다고 느끼기 때문이다. 간선이 많은 경우는 프림, 간선의 개수 적은 경우는 크루스칼을 사용하는 것이 효율적이라 한다. 프림 알고리즘은 다익스트라 알고리즘과 비슷한 점이 많다. 왜냐하면 하나의 시작점에서 연결된 다른 점들을 확인하는 과정이기 때문이다. 

import sys
import heapq 

n= int(input())
visited = [0 for _ in range(n+1)]
gra=[[] for _ in range(n+1)]
for i in range(1,1+n):
    oneline = list(map(int, input().split()))
    for j in range(i, len(oneline)):
        if oneline[j] ==0:
            continue 
        gra[i].append((j+1, oneline[j]))
        gra[j+1].append((i, oneline[j]))
# print(gra)
ans =0 
def prim(start):
    global ans 
    q =[[0,start]]
    heapq.heapify(q)
    while q:
        cost, now =heapq.heappop(q)
        if(visited[now] ==0):
            
            visited[now] = 1 
            ans += cost 
            for nextnode,nextcost in gra[now]:
                if visited[nextnode] == 0 :
                    heapq.heappush(q, (nextcost , nextnode))
                
prim(1)
print(ans)