Tip
- 최소 스패닝 트리코드는 그냥 외우기!!!!
- 중요한 건 해당 문제가 MST 문제인지 알아내는 능력
- 모든 노드가 연결되도록한다거나
- 이미 연결된 노드를 최소의 비용으로 줄이기
MST
- Minimum Spanning Tree
- Spanning Tree : 모든 노드가 연결된 트리
- MST : 최소의 비용으로 모든 노드가 연결된 트리
- 어떻게 해야 최소의 간선으로 모든 노드를 연결할 수 있는지가 관건.
MST 푸는 방법 : Kruskal or Prim
- Kruskal : 전체 간선 중 작은 것부터 연결 (Union-Find로 구현이 가능하지만 복잡.)
- Prim : 현재 연결된 트리에 이어진 간선중 가장 작은 것을 추가. (상대적으로 구현 간단.)
- 가장 작은 것을 비교해주는 자료구조를 heap으로 사용.
- heap은 최소, 최대값을 빠르게 구할 수 있음.
- heap
- 최대값, 최소값을 빠르게 계산하기 위한 자료구조
- 이진 트리 구조
- 처음엔 저장할때부터 최대값 or 최소값 결정하도록
- 입력(삽입), 삭제시 logE의 시간복잡도를 가짐.
# [비용, 노드]
heap = [[0,1]]
while heap:
w,next_node = heapq.heappop(heap)
# 확인 안한 노드일 경우에만 동작.
if chk[next_node] == False:
chk[next_node] = True
# result값에 남는 값만 추가가 됨.
rs+=w
#연결되지 않은 edge인지 확인하고 아니라면 q에 넣음.
for next_edge in edge[next_node]:
if chk[next_edge[1]] == False:
heapq.heappush(heap, next_edge)
mst는 코드를 외워놓기.
그대로 대입.
mst는 보통 간선이 양방향그래프임.
IDEA
- 최소 스패닝 트리기본문제 암기
- 간선을 인접 리스트 형태로 저장
- 간선 = 어디에서 어디까지 얼마의 비용을 저장할 지 결정한 것.
- w = 비용, v = 노드
- 인접리스트 = [ 1 [ ( w, v ), ~, ~] 2 [ ( w, v ), ~, ~] ....] 이런 식으로 인접리스트 형태로 저장.
- 시작점부터 힙에 넣기
- 힙이 빌때까지,
- 해당 노드 방문 안한 곳일 경우
- 방문체크, 비용추가, 연결된 간선 새롭게 추가.
시간복잡도(암기)
- MST 시간복잡도 = O (E log E) 암기!!
- Edge (인접)리스트에 저장 : O (E)
- Heap 안 모든 Edge에 연결된 간선 확인 : O(E+E)
- 모든 간선 힙에 삽입 : O(ElgE) -> 모든 간선에 삽입해야함으로 lgE X E = ElgE
- O ( E + 2E + ElgE ) = O( 3E + ElgE ) = O(E(3+lgE)) = O(ElgE)
자료구조
- Edge 저장 리스트 (int, int)[] <= 리스트 (무게, 다음노드)[]
- 처음엔 edge(간선)을 저장할 수 있는 인접리스트가 있어야함.
- 무게는 항상 앞에!! 왜냐면 heap에서 항상 최소값을 앞의 값에서 찾아주기 때문.
=> 무게가 최소값인게 의미가 있지 노드값은 상관없으므로 항상 앞은 무게!- 무게 최대 : 1e6 > INT 가능
- 정점 번호 최대 : 1e4 > INT 가능.
- 정점 방문 : bool[]
- MST 비용 : int(최대2^31보다 이내) > 스패닝트리의 가중치범위를 int값 내로 문제에서 제시해줌.
"""
1. 아이디어
- MST 기본문제, 암기
- 간선을 인접리스트에 집어넣기
- 힙에 시작점 넣기
- 힙이 빌때까지 다음의 작업을 반복
- 힙의 최소값 꺼내서, 해당 노드방문 안했다면
- 방문표시, 해당 비용추가, 연결된 간선들 힙에 넣어주기
2. 시간복잡도
- MST : O(ElgE)
3. 자료구조
- 간선 저장 되는 인접리스트 : (무게, 노드번호)
- 힙 : (무게, 노드번호)
- 방문여부 : bool[]
- MST 결과값 : int
"""
import sys
import heapq
input = sys.stdin.readline
V,E = map(int, input().split())
# 인접리스트는 인덱스를 바로쓰기 위해 V+1개의 리스트가 필요.
edge = [[] for _ in range(V+1)]
chk = [False] * (V+1)
rs = 0
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]]
while heap:
w, each_node = heapq.heappop(heap)
if chk[each_node] == False:
chk[each_node] = True
rs += w
for next_edge in edge[each_node]:
if chk[next_edge[1]] == False:
heapq.heappush(heap, next_edge)
print(rs)