[백준] 1197 최소 스패닝 트리(Python)

백준 - 1197 최소 스패닝 트리

풀이

프림 알고리즘
1. bfs와 비슷하지만 우선순위큐를 사용해서 가중치 기준으로 정렬, 접근
2. 스패닝트리의 간선의 개수는 점의 개수 - 1 !!!!!!! -> 간선의 개수를 세서 break

코드

from sys import stdin
from heapq import heappop, heappush, heapify

V, E = map(int, stdin.readline().split())

visited = [0] * (V + 1)
graph = [[] for i in range(V + 1)]

for i in range(E):
    a, b, v = map(int, stdin.readline().split())
    graph[a].append((v, b))
    graph[b].append((v, a))

cnt = 0
answer = 0
q = []
heappush(q, (0, 1))
while q:
    if cnt == V:
        break
    value, vertex = heappop(q)
    if not visited[vertex]:
        visited[vertex] = 1
        cnt += 1
        answer += value
        for i in graph[vertex]:
            heappush(q, i)

print(answer)