[BOJ/백준 코딩] 최소 스패닝 트리 - PYTHON #1197

소스 코드

import sys
import heapq
input = sys.stdin.readline
 
v,e = map(int, input().split())
visited = [False]*(v+1)
board = [[] for _ in range(v+1)]
tmp = [[0, 1]]
for _ in range(e):
    start, end, w = map(int, input().split())
    board[start].append([w, end])
    board[end].append([w, start])
 
ans = 0
cnt = 0
while tmp:
    if cnt == v:
        break
    w, s = heapq.heappop(tmp)
    if not visited[s]:
        visited[s] = True
        ans += w
        cnt += 1
        for i in board[s]:
            heapq.heappush(tmp, i)
 
print(ans)

 

---

해결 방법

1. 프림알고리즘

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.