[백준] 1197_최소 스패닝 트리 (prim 이용)

📕 문제

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

1197번: 최소 스패닝 트리

 

💡 풀이법

1. 간선의 정보들을 edges에 담는다.

2. visited 리스트는 노드들의 방문 처리를 할 리스트이다.

3. 1을 넣고 find_MST 함수를 실행시킨다.

4. 1을 방문처리해주고 1과 인접한 노드들을 candidate 리스트로 만든다.

5. candidate를 heap 구조로 만들어준다. ( 가장 가중치가 작은 간선을 꺼내기 위해)

6. candidate에서 하나를 pop해서 방문하지 않았다면 방문처리를 해주고 ans에 가중치를 더해준다.

7. 위에서 뺀 노드와 인접한 노드들을 확인하면서 방문하지 않았다면 candidate에 넣어준다.

 

import heapq
from collections import defaultdict

def find_MST(s):
    global ans
    visited[s] = 1
    candidate = edges[s]
    heapq.heapify(candidate)

    while candidate:
        w, n = heapq.heappop(candidate)

        if not visited[n]:
            visited[n] = 1
            ans += w
            
            for edge in edges[n]:
                if not visited[edge[1]]:
                    heapq.heappush(candidate, edge)

V, E = map(int, input().split())
edges = defaultdict(list)
for _ in range(E):
    n1, n2, w = map(int, input().split())
    edges[n1].append((w, n2))
    edges[n2].append((w, n1))
visited = [0] * (V+1)
ans = 0
find_MST(1)
print(ans)