해킹왕 양선규

신장 트리(Spanning Tree) - 그래프 내의 모든 정점을 포함하면서 사이클이 없는 부분 트리 최소 스패닝(신장) 트리(Minimum Spanning Tree, MST) - 가중치가 있는 양방향 그래프에서 싸이클 없이 모든 정점을 포함하며 가중치의 합이 최소인 트리 - 모든 정점을 연결하는 트리를 형성하면서, 가중치 합이 최소화되도록 하는 것 프림(Prim) 알고리즘 - 크루스칼 알고리즘과 더불어 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘 - 가중치가 작은 순으로 노드를 그래프에 포함시켜야 하기 때문에 우선순위 큐를 사용한다. - 이미 그래프에 속한 노드엔 적용시키지 않기 위해 visited를 사용한다. 프림 알고리즘 동작원리 1. 임의의 시작 노드를 설정하고 T(트리)..

import heapq import sys input = sys.stdin.readline N, E = map(int, input().split()) # 노드, 간선 graph = [[] for _ in range(N + 1)] # 그래프 입력받기 for _ in range(E): a, b, c = map(int, input().split()) graph[a].append((c, b)) graph[b].append((c, a)) visited = [False] * (N + 1) # 방문체크 리스트 def prim(graph, start): # 그래프, 시작노드 입력받는다, 프림 알고리즘 사용 visited[start] = True # 시작노드 방문체크 distance = 0 # 거리(가중치)를 계산할 변..