LeetCode/NeetCode

[최소신장트리 MST] Prim's minimum spanning tree

hyunkookim 2025. 4. 11. 06:15

 

Prim's Algorithm

Solved 

Hard

Implement Prim's minimum spanning tree algorithm.

A Minimum Spanning Tree (MST) is a tree that spans all the vertices in a given weighted, undirected graph while minimizing the total edge weight and avoiding cycles. It connects all nodes with exactly ∣V∣−1 edges, where V is the set of vertices, and has the lowest possible sum of edge weights.

Prim's algorithm is a greedy algorithm that builds the MST of a graph starting from an arbitrary vertex. At each step, the algorithm adds the lightest edge connecting a vertex in the MST to a vertex outside the MST, effectively "growing" the MST one edge at a time.

Objective:

Given a weighted, undirected graph, find the minimum spanning tree (MST) using Prim's algorithm and return its total weight. If the graph is not connected, the total weight of the minimum spanning tree should be -1.

Input:

  • n - the number of vertices in the graph, where (2 <= n <= 100). Each vertex is labeled from 0 to n - 1.
  • edges - a list of tuples, each representing an undirected edge in the form (u, v, w), where u and v are vertices connected by the edge, and w is the weight of the edge, where (1 <= w <= 10).

✅ 문제 설명 (Prim's 최소 신장 트리 알고리즘 구현)

🌲 최소 신장 트리 (MST: Minimum Spanning Tree)란?

  • 가중치가 있는 무방향 그래프에서,
  • 모든 정점(노드)을 연결하면서,
  • 사이클 없이,
  • 간선들의 가중치 합이 최소가 되도록 구성된 트리를 말합니다.
  • MST는 항상 정점의 개수 |V|에 대해 (|V| - 1)개의 간선을 가집니다.

💡 Prim's 알고리즘이란?

  • Greedy 알고리즘 중 하나로, MST를 점진적으로 만들어 나갑니다.
  • 아무 정점에서 시작해서,
  • 매 단계마다 MST 안의 정점에서 MST 밖의 정점으로 연결되는 간선 중 가장 가중치가 작은 간선을 선택해 연결합니다.
  • 이렇게 하나씩 간선을 추가하면서 MST를 확장합니다.

🎯 목표

  • 주어진 가중치가 있는 무방향 그래프에 대해,
  • Prim’s 알고리즘을 사용하여 최소 신장 트리(MST)를 구성하고,
  • 그 총 가중치의 합을 반환하세요.
  • 만약 그래프가 연결되어 있지 않아 MST를 구성할 수 없다면, -1을 반환하세요.

📥 입력

  • n: 정점(노드)의 개수 (2 ≤ n ≤ 100)
    • 노드 번호는 0부터 n - 1까지입니다.
  • edges: 간선들의 리스트로,
    각 간선은 (u, v, w) 형태의 튜플입니다.
    • u와 v: 간선으로 연결된 두 정점
    • w: 그 간선의 가중치 (1 ≤ w ≤ 10)
import heapq
from typing import List

class Solution:
    def minimumSpanningTree(self, n: int, edges: List[List[int]]) -> int:
        # 각 정점은 0부터 n - 1까지의 번호로 구성됨
        
        adj = {}  # 인접 리스트를 딕셔너리로 표현
        for i in range(n):
            adj[i] = []  # 각 노드에 대해 빈 리스트 초기화

        # 간선 정보 추가 (무방향 그래프이므로 양방향으로 저장)
        # edges는 [시작노드, 끝노드, 가중치] 형태
        for s, e, w in edges:
            adj[s].append([e, w])  # s → e로 가는 간선
            adj[e].append([s, w])  # e → s로 가는 간선 (무방향)

        mst = []        # 최소 신장 트리에 포함되는 간선 목록
        minCost = 0     # 최소 신장 트리의 총 가중치
        visit = set()   # 방문한 노드 집합
        minHeap = []    # [가중치, 시작노드, 도착노드] 형식의 최소 힙

        # 0번 노드부터 시작 (임의의 노드에서 시작 가능)
        visit.add(0)    # 0번 노드를 방문 처리
        for neighbor, weight in adj[0]:
            heapq.heappush(minHeap, [weight, 0, neighbor])  # 0번에서 갈 수 있는 간선들을 힙에 추가

        # 모든 노드를 방문할 때까지, 그리고 힙이 비어있지 않을 때까지 반복
        while len(visit) < n and minHeap:
            w, sn, en = heapq.heappop(minHeap)  # 가장 가중치가 낮은 간선 선택
            if en in visit:
                continue  # 이미 방문한 노드는 스킵

            # 선택한 간선을 MST에 추가
            mst.append([sn, en])
            visit.add(en)      # 새 노드를 방문 처리
            minCost += w       # 가중치 누적

            # 새로 방문한 노드에서 연결된 간선들 중 아직 방문하지 않은 노드로 가는 간선만 힙에 추가
            for nei, wei in adj[en]:
                if nei not in visit:
                    heapq.heappush(minHeap, [wei, en, nei])

        # MST가 완성되었는지 확인: 간선이 정확히 (n - 1)개여야 함
        # 그렇지 않으면 연결되지 않은 그래프임
        return minCost if len(mst) == n - 1 else -1

 

✅ 핵심 포인트 정리

항목 설명
visit 현재 MST에 포함된 노드 집합 (사이클 방지 및 방문 추적)
minHeap 항상 가장 작은 가중치 간선을 선택하기 위한 자료구조
mst 최소 신장 트리에 포함된 간선 추적 (디버깅이나 시각화 용도로 사용 가능)
minCost 선택된 간선들의 총 비용 (최소 신장 트리의 비용)
len(mst) == n - 1 최소 신장 트리는 항상 n - 1개의 간선으로 구성되어야 함

 

중요 참고 사항!!

while minHeap: 이것만해도 정상 동작하는데?
 

ChatGPT의 말:

아주 좋은 관찰이에요! 👏
맞아요, while minHeap:만 써도 대부분의 경우 정상 동작합니다.
하지만 그 안에 숨겨진 의미와 안전성 차이가 있어요.

✅ while minHeap:

이건 그냥 "힙에 간선이 남아있는 동안만 반복" 하겠다는 뜻이에요.

  • MST를 만들기 위해 필요한 만큼의 간선이 선택되었는지 확인하지 않음
  • **불완전한 그래프(연결되지 않은 그래프)**에서도 종료 조건 없이 계속 반복할 수 있음
    → 단, 방문한 노드 수가 부족한 상태에서 힙이 비면 heappop에서 오류 발생 없이 종료됨
  • 결과적으로는 MST가 완성되지 않았는데도 minCost를 반환할 수 있음
    → 위험함!

✅ while len(visit) < n and minHeap:

이건 MST가 만들어져야 하는 정확한 조건을 체크합니다.

  • 전체 노드를 다 방문했는지 (len(visit) < n)
  • 아직 방문할 수 있는 간선이 있는지 (minHeap이 비어있지 않은지)
  • 이 조건이 만족되지 않으면, 불완전한 MST라고 판단해서
    → 마지막에 return -1 을 수행함

✅ 예를 들어보자:

python
복사편집
n = 4 edges = [ [0, 1, 1], [1, 2, 2] # 3번 노드가 완전히 단절됨 ]

while minHeap: 사용 시

  • 0 → 1 → 2는 방문되고 종료
  • minCost = 3 리턴됨
    ❌ 하지만 3번 노드는 방문되지 않았으므로 MST가 아님

while len(visit) < n and minHeap: 사용 시

  • visit에 0, 1, 2만 있음
  • 더 이상 minHeap에 간선 없음
  • 반복문 종료 → len(mst) == n - 1 검사 실패 → -1 리턴
    ✅ 올바른 처리!

✅ 결론

조건 안전성 연결 확인 권장 여부
while minHeap: ❌ 낮음 ❌ 안함 ❌ 추천 안함
while len(visit) < n and minHeap: ✅ 높음 ✅ 함 ✅ 강력 추천

 

정리:
Prim's 알고리즘에서 그래프가 항상 연결되어 있다는 보장이 없다면,
while len(visit) < n and minHeap:이 정확하고 안정한 조건입니다.