[BOJ] 1197. 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

 

 

1. 해결방법

"""
1. 아이디어
- MST 기본문제 : 외우기
- 간선을 인접리스트에 삽입
- 힙에 시작점 삽입
- 힙이 빌때까지 다음 작업을 반복
    - 힙의 최솟값을 꺼내서 해당 노드에 방문 여부를 확인하고 안했다면,
        - 방문 표시, 해당 비용 더, 연결된 간선들 힙에 삽입

2. 시간복잡도
- O(ElogE)

3. 자료구조
- 간선 저장 되는 인적리스트 : (무게, 노드 번호)
- 힙 : (무게, 노드 번호)
- 방문 여부 : bool[]
- MST 결과값 : int
"""

 

 

2. 정답코드

import sys
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())

# 인접리스트
edge = [[] for _ in range(V + 1)]

for i in range(E):
    a, b, c = map(int, input().split())
    # 양방향이기 떄문에 둘다 집어넣음
    edge[a].append([c, b])
    edge[b].append([c, a])


heap = [[0, 1]]
chk = [False] * (V + 1)
result = 0

while heap:
    w, each_node = heapq.heappop(heap)

    # 힙에서 꺼내오면 방문 여부부터 확인
    if chk[each_node] == False:
        chk[each_node] = True
        result += w
        for next_node in edge[each_node]:

            # 인접 리스트에서 가져온 노드가 방문을 안했다면,
            if chk[next_node[1]] == False:
                heapq.heappush(heap, next_node)

print(result)

MST Prim 알고리즘 방식의 기본 유형이다.
일단 이문제는 그냥 외우는게 좋다. 외우고 이를 토대로 응용을 하면 된다.