# BOJ - 1197 - 최소 스패닝 트리

Updated:

```
import sys
import heapq
def PRIM(graph, V, idx):
hq = []
visit = [False] * (V + 1)
visit[idx] = True
distance = 0
cnt = 1
for i in graph[idx]:
heapq.heappush(hq, i)
while hq:
weight, vertex = heapq.heappop(hq)
if not visit[vertex]:
visit[vertex] = True
cnt += 1
distance += weight
for i in graph[vertex]:
heapq.heappush(hq, i)
if cnt == V:
return distance
return 0
def solution():
V, E = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(V + 1)]
for _ in range(E):
A, B, C = map(int, sys.stdin.readline().split())
graph[A].append((C, B))
graph[B].append((C, A))
print(PRIM(graph, V, 1))
solution()
```

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

## Leave a comment