[백준] 1922번, 네트워크 연결 (Python)

문제

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

코드

import heapq
n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
answer = 0

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

queue = []
heapq.heappush(queue, (0,1))

def Prim():
    global answer
    while queue:
        wei, now = heapq.heappop(queue)
        if visited[now] == False:
            visited[now] = True
            answer += wei
            for next_wei, next_node in graph[now]:
                heapq.heappush(queue, (next_wei, next_node))
    return answer

print(Prim())

 

모든 정점을 연결하는 가장 작은 최소비용을 구해야한다. 모든 정점을 연결하는 최소 연결 횟수는 n-1개 이고 n-1개의 간선으로 연결되어 있으면 트리형태를 가지고있어 스패닝트리 문제이다.

 

스패닝트리에 크루스칼과 프림이 있는데 프림으로 문제를 풀어보았다.

 

Prim은 다익스트라 코드와 유사하다고 생각하는데 차이점은 다익스트라는 한 정점에서 최소비용이 드는 순서대로 모두 방문하는데

 

Prim은 한 정점에서 연결된 부분중 가장 작은 비용이 드는 한가지 정점으로만 이동한다. 

 

방문체크를 해줘서 n-1만큼 이동한후 종료된다.