[코딩테스트] 백준 1197번: 최소 스패닝 트리

1. 아이디어

▪ 간선을 인접리스트에 넣기

▪ heap에 시작점 (0,1) 추가하기

▪ heap이 빌때까지 노드를 꺼내서 다음을 반복

   - 힙의 최소값을 꺼내고, 해당 노드를 방문하지 않았으면

      - 방문여부 갱신

      - 가중치 합 갱신

      - 방문하지 않은 간선들 heap에 추가

2. 시간복잡도

▪ O(ElogE)

3. 변수

▪ 간선의 정보를 저장할 인접리스트 (가중치,다음노드): (int,int)[][]

▪ 방문 여부: bool[]

▪ 가중치의 합: int

▪ (가중치,노드)를 저장할 heap

4. 오답노트

▪ 인접 리스트 만들때 양방향으로 만들어야함

Code

import sys
import heapq

input = sys.stdin.readline

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

edges = [[] for _ in range(V+1)]
for _ in range(E):
    a,b,c = map(int, input().split())
    edges[a].append([c,b])
    edges[b].append([c,a]) # 오답노트

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

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

    if chk[node] == False:
        chk[node] = True
        weight_sum += w

        for next_edge in edges[node]:
            if chk[next_edge[1]] == False:
                heapq.heappush(heap,next_edge)

print(weight_sum)

 

1197번: 최소 스패닝 트리