프림 알고리즘 (Prim's Algorithm)

입력:
8 10
1 2 13
1 3 15
1 8 17
2 7 4
3 4 11
3 5 13
4 5 12
5 8 9
6 7 3
7 8 6

import heapq

heap = []
heapq.heappush(heap, (13, 2))  # 가중치 13, 노드 2
heapq.heappush(heap, (4,  7))  # 가중치 4,  노드 7
heapq.heappush(heap, (15, 3))  # 가중치 15, 노드 3

weight, node = heapq.heappop(heap)
# → weight=4, node=7  (최솟값 먼저 꺼냄)

import sys
import heapq

input = sys.stdin.readline

def prim(start):
    visited[start] = True
    route = [start]
    heap = graph[start][:]     # 시작 노드의 인접 간선을 힙에 삽입
    heapq.heapify(heap)        # 리스트를 힙으로 변환
    total_weight = 0

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

        if visited[node]:      # 이미 방문한 노드는 건너뜀
            continue

        visited[node] = True
        route.append(node)
        total_weight += weight

        for edge in graph[node]:
            if not visited[edge[1]]:
                heapq.heappush(heap, edge)

    return route, total_weight


v, e = map(int, input().split())
graph   = [[] for _ in range(v + 1)]
visited = [False] * (v + 1)

for _ in range(e):
    u, w, weight = map(int, input().split())
    # 무방향 그래프 — 양방향 모두 저장
    graph[u].append([weight, w])
    graph[w].append([weight, u])

route, total = prim(1)
print(f"방문 순서: {route}")
print(f"MST 총 가중치: {total}")

# 출력:
# 방문 순서: [1, 2, 7, 6, 8, 5, 4, 3]
# MST 총 가중치: 58

1. 시작 노드를 visited 처리하고, 인접 간선을 모두 힙에 넣는다
2. 힙에서 (최소 가중치, 노드)를 꺼낸다
3. 이미 방문한 노드면 skip
4. 방문하지 않은 노드면:
   a. visited 처리
   b. 가중치를 누적
   c. 해당 노드의 인접 간선 중 미방문 노드만 힙에 추가
5. 힙이 빌 때까지 2~4를 반복

# ✅ 올바른 형태 — heapq가 가중치 기준으로 정렬
graph[u].append([weight, v])

# ❌ 잘못된 형태 — 노드 번호 기준으로 정렬됨
graph[u].append([v, weight])

# heappop 후 반드시 visited 확인
weight, node = heapq.heappop(heap)
if visited[node]:
    continue  # 이미 MST에 포함된 노드 — 건너뜀

# 양쪽 방향 모두 저장
graph[u].append([weight, v])
graph[v].append([weight, u])