핵심 인사이트 (3줄 요약)

  1. 본질: 프림 알고리즘 (Prim's Algorithm)은 최소 신장 트리 (MST, Minimum Spanning Tree) 문제에서, 이미 선택한 정점 집합과 바깥 정점을 잇는 간선 중 가장 가벼운 간선을 반복해서 추가하며 하나의 트리를 키워 가는 탐욕 알고리즘이다.
  2. 가치: 인접 리스트와 우선순위 큐를 쓰면 시간 복잡도는 보통 O(E log V)가 되며, 간선을 모두 정렬하지 않고도 현재 경계(frontier)만 관리하면 되므로 큰 그래프에서도 실용적이다.
  3. 판단 포인트: 연결된 무방향 가중치 그래프에서 전체 연결 비용 최소화가 목표일 때 적합하며, 최단 경로 문제와 혼동하지 말아야 하고, 그래프 밀도와 자료구조에 따라 크루스칼 (Kruskal) 과 선택 기준이 달라진다.

Ⅰ. 개요 및 필요성

프림 알고리즘은 모든 정점을 사이클 없이 연결하되 전체 간선 가중치 합이 최소가 되도록 하는 MST 문제를 푸는 대표적인 방법이다. 핵심은 여러 개의 작은 부분 트리를 나중에 합치는 것이 아니라, 시작 정점에서 출발해 하나의 트리를 계속 확장한다는 점에 있다.

이 알고리즘이 필요한 이유는 "각 출발점에서 가장 가까운 길"이 아니라 "전체 네트워크를 가장 적은 비용으로 연결하는 길"이 필요하기 때문이다. 전력망, 통신망, 도로, 배관, 배선 설계에서는 어느 한 정점까지의 최단 거리보다 전체 설치 비용의 최소화가 더 중요하다. 이때 프림은 현재 트리 바깥으로 나가는 가장 싼 연결선만 계속 고르면 된다는 단순한 규칙으로 문제를 푼다.

프림이 직관적으로 강한 이유는 경계 간선을 본다는 점이다. 이미 선택된 정점 집합을 S 라고 하면, 프림은 항상 S 와 V-S 를 잇는 간선 중 최소 가중치를 고른다. 이 선택이 안전하다는 것이 컷 속성 (Cut Property) 이고, 프림의 정당성은 여기에 기대고 있다.

아래 그림은 프림이 "한 번에 한 정점씩" 트리를 키우는 모습을 보여 준다.

┌──────────────────────────────────────────────────────────────────────┐
│          Prim keeps one growing tree and a frontier of edges         │
├──────────────────────────────────────────────────────────────────────┤
│ Start S = {A}                                                        │
│ frontier : A-B(4), A-C(2), A-D(7)                                    │
│ pick min : A-C(2) -> S = {A,C}                                       │
│ frontier : A-B(4), C-D(3), C-E(6)                                    │
│ pick min : C-D(3) -> S = {A,C,D}                                     │
└──────────────────────────────────────────────────────────────────────┘

여기서 중요한 것은 "현재 가장 싼 간선"이 아니라 현재 트리 밖으로 나가는 간선 중 가장 싼 것이라는 점이다. 그래야 사이클을 만들지 않으면서 전체 비용 최소 조건을 유지할 수 있다.

  • 📢 섹션 요약 비유: 프림 알고리즘은 마을 하나에서 시작해 가장 싸게 이웃 마을과 다리를 놓고, 그다음 새로 연결된 마을에서 다시 가장 싼 다리를 찾는 식으로 동네를 넓혀 가는 방법과 같다.

Ⅱ. 아키텍처 및 핵심 원리

프림 알고리즘의 내부 상태는 비교적 단순하다. 어떤 정점이 이미 트리에 포함되었는지, 각 바깥 정점이 현재 트리와 연결되는 최소 비용이 얼마인지, 그리고 그 연결을 만든 부모 정점이 누구인지만 관리하면 된다. 이 정보를 효율적으로 유지하기 위해 우선순위 큐를 사용한다.

구성 요소의미역할
방문 집합 inMST트리에 포함된 정점 여부사이클 방지와 경계 판단
key[v]현재 트리와 정점 v 를 잇는 최소 간선 비용다음에 선택할 후보 우선순위
parent[v]v 를 트리에 연결한 정점MST 간선 복원
우선순위 큐key 가 가장 작은 정점 추출O(log V)로 경계 갱신

프림의 핵심 메커니즘은 다음과 같다. 시작 정점의 key 를 0으로 두고 우선순위 큐에 넣는다. 가장 작은 key 를 가진 정점을 꺼내 트리에 포함시킨 뒤, 그 정점과 연결된 이웃을 검사한다. 이웃이 아직 트리 밖에 있고, 현재 간선이 그 이웃의 기존 key 보다 작으면 key 와 parent 를 갱신한다. 이 과정을 반복하면 결국 모든 정점이 트리에 들어간다.

이 과정을 정당화하는 이론이 컷 속성이다. 현재 트리 정점 집합 S 와 나머지 정점 집합 V-S 를 가르는 컷이 있을 때, 그 컷을 가로지르는 가장 작은 간선은 어떤 MST 에도 안전하게 포함될 수 있다. 프림은 매 단계마다 바로 이 "안전한 간선"을 하나씩 추가하는 방식이다.

┌──────────────────────────────────────────────────────────────────────┐
│               Safe edge = cheapest edge crossing the cut             │
├──────────────────────────────────────────────────────────────────────┤
│ Tree S = {A,C,D}                                                     │
│ crossing edges : A-B(5), D-E(4), C-F(6)                              │
│                                                                      │
│ cheapest crossing edge = D-E(4)                                      │
│ -> add E to the tree, keep MST property                              │
└──────────────────────────────────────────────────────────────────────┘

자료구조에 따라 성능도 달라진다. 인접 행렬을 쓰면 구현은 단순하지만 O(V^2)가 된다. 인접 리스트 + 이진 힙 기반 우선순위 큐를 쓰면 보통 O(E log V)이고, 피보나치 힙 (Fibonacci Heap) 을 쓰면 이론적으로 O(E + V log V)까지 내려간다. 실무와 코딩 테스트에서는 대개 인접 리스트 + 이진 힙 조합이 가장 균형이 좋다.

  • 📢 섹션 요약 비유: 이미 만든 길에서 바깥으로 나가는 문들만 보고 가장 싼 문을 하나씩 여는 방식이 프림이다. 방 전체를 다시 검사하지 않고 문 앞 가격표만 갱신해 가는 것이 우선순위 큐의 역할이다.

Ⅲ. 비교 및 연결

프림은 MST 알고리즘이지만, 구조가 다익스트라 (Dijkstra) 와 비슷해 자주 헷갈린다. 둘 다 우선순위 큐를 사용해 가장 작은 값을 가진 정점을 꺼내 확정한다. 그러나 다익스트라는 "시작점에서의 누적 거리"를 최소화하고, 프림은 "현재 트리에 연결되는 간선 비용"을 최소화한다는 점에서 목적 함수가 다르다.

비교 축프림 (Prim)크루스칼 (Kruskal)다익스트라 (Dijkstra)
목표MST 생성MST 생성단일 시작점 최단 경로
선택 단위정점 경계의 최소 간선전체 간선 중 최소 간선누적 거리 최소 정점
핵심 자료구조우선순위 큐간선 정렬 + 유니온 파인드우선순위 큐
그래프 적합성밀집 그래프에서 자주 유리희소 그래프에서 자주 유리경로 탐색 문제
주의점연결 그래프 전제사이클 판정 필수MST 문제에는 부적합

프림과 크루스칼의 가장 큰 차이는 "하나의 트리를 키우느냐"와 "간선을 전역에서 고르느냐"다. 프림은 현재 트리에 인접한 간선만 보면 되므로, 그래프가 인접 리스트나 인접 행렬 형태로 주어졌을 때 자연스럽다. 크루스칼은 간선 전체를 정렬한 뒤 사이클이 생기지 않는 선에서 선택하므로, 간선 목록이 이미 주어져 있고 희소 그래프인 경우 구현이 간단하다.

또한 프림은 음수 가중치가 있어도 MST 문제 자체에는 적용 가능하다. 최단 경로처럼 누적 거리 비교를 하지 않기 때문이다. 다만 그래프가 연결되어 있지 않다면 하나의 MST 가 아니라 최소 신장 포리스트 (MSF, Minimum Spanning Forest) 만 구할 수 있다는 점은 분명히 해야 한다.

  • 📢 섹션 요약 비유: 프림이 동네를 한 구역씩 넓혀 가는 도시 확장 계획이라면, 크루스칼은 도시 전체 지도에서 가장 싼 도로부터 차례로 고르는 방식이다. 다익스트라는 아예 "우리 집에서 어디까지 제일 빨리 가나"를 보는 다른 문제다.

Ⅳ. 실무 적용 및 기술사 판단

프림 알고리즘은 통신망, 배전망, 상수도망, 광케이블 배치처럼 전체 연결 비용을 최소화해야 하는 문제에서 자주 등장한다. 예를 들어 여러 공장 건물을 광케이블로 연결할 때, 각 건물 간 공사비가 주어졌다면 프림은 이미 연결된 건물 묶음에서 바깥 건물로 나가는 가장 싼 링크만 계속 추가하며 전체 비용 최소 해를 구할 수 있다.

실무적 판단에서는 그래프 표현 방식이 중요하다. 인접 행렬로 주어진 비교적 밀집한 그래프라면 O(V^2) 프림도 충분히 빠르다. 반대로 정점 수는 크고 간선 수는 상대적으로 적은 희소 그래프라면 인접 리스트 + 우선순위 큐 프림이나 크루스칼을 비교해 선택해야 한다.

기술사 판단 체크리스트

  1. 그래프가 무방향이며 연결되어 있는가?
  2. 문제 목표가 "전체 연결 비용 최소"인지, "특정 출발점 최단 경로"인지 구분했는가?
  3. 입력이 인접 리스트인지, 인접 행렬인지, 간선 목록인지에 맞는 구현을 택했는가?
  4. 그래프가 희소한지 밀집한지에 따라 프림과 크루스칼을 비교했는가?
  5. 연결 그래프가 아니라면 MST 가 아니라 MSF 를 구해야 함을 명시했는가?

채택 / 회피 판단

  • 채택: 연결된 무방향 가중치 그래프, 인접 구조가 자연스러운 네트워크 설계 문제, 밀집 그래프
  • 조건부 채택: 희소 그래프에서도 우선순위 큐 구현이 편한 경우
  • 회피: 방향 그래프, 최단 경로 문제, 연결 여부가 불분명한데 단일 MST 를 요구하는 경우

자주 나오는 안티패턴

  • 프림을 다익스트라처럼 누적 거리 문제에 적용하는 경우
  • 이미 트리에 들어간 정점을 다시 연결해 사이클을 허용하는 구현 실수
  • 우선순위 큐의 오래된 항목을 처리하면서 방문 여부 검사를 빠뜨리는 경우
  • 비연결 그래프인데도 결과를 MST 라고 단정하는 경우

실무와 시험 모두에서 가장 흔한 함정은 "프림 = 가까운 정점 선택"이라는 막연한 기억이다. 정확한 기억은 현재 트리와 바깥을 잇는 최소 간선 선택이다. 이 차이를 분명히 이해해야 증명, 구현, 비교 문제에서 흔들리지 않는다.

  • 📢 섹션 요약 비유: 동네 전체에 전선을 놓을 때, 이미 연결된 집들 울타리 밖으로 나가는 전선 중 가장 싼 것만 계속 고르는 방식이 프림이다. 집마다 가장 가까운 가게를 찾는 문제와는 다르다.

Ⅴ. 기대효과 및 결론

프림 알고리즘의 장점은 하나의 트리를 일관되게 확장하므로 직관이 좋고, 우선순위 큐와 결합했을 때 실용적인 성능을 낸다는 점이다. 특히 네트워크 전체를 최소 비용으로 연결해야 하는 문제에서, 간선을 전부 다시 정렬하지 않고도 해를 키워 갈 수 있다는 장점이 있다.

한계도 분명하다. 그래프가 비연결이면 단일 MST 를 만들 수 없고, 문제 목표가 최단 경로라면 프림은 정답을 보장하지 않는다. 또한 동적 그래프나 간선이 계속 추가·삭제되는 환경에서는 정적 MST 알고리즘만으로는 충분하지 않을 수 있다.

결론적으로 프림은 "정점 하나에서 출발해 가장 싼 경계 간선으로 나무를 키운다"는 한 문장으로 기억하면 좋다. MST 문제를 만나면 먼저 컷 속성과 그래프 표현 방식을 떠올리고, 그다음 크루스칼과의 적합성을 비교하는 것이 올바른 접근이다.

  • 📢 섹션 요약 비유: 프림 알고리즘은 작은 마을에서 시작해 가장 싸게 이어 붙일 수 있는 다리만 고르며 나라 전체 지도를 완성하는 방식이라고 기억하면 된다.

📌 관련 개념 맵

개념연결 포인트
최소 신장 트리 (MST, Minimum Spanning Tree)프림이 해결하는 직접 대상 문제
컷 속성 (Cut Property)프림의 탐욕 선택이 안전함을 보장하는 이론
우선순위 큐현재 경계에서 최소 비용 정점을 빠르게 선택
크루스칼 (Kruskal)같은 MST 문제를 간선 중심으로 푸는 비교 대상
유니온 파인드크루스칼에서 사이클 판정에 쓰이는 연결 자료구조
다익스트라 (Dijkstra)구조는 비슷하지만 목표 함수가 다른 알고리즘

📈 관련 키워드 및 발전 흐름도

Weighted undirected graph
    │
    ▼
MST (Minimum Spanning Tree)
    │
    ├─ edge sorting + Union-Find -> Kruskal
    └─ frontier minimum + priority queue -> Prim
    │
    ▼
Network design, clustering, infrastructure spanning

이 흐름은 가중치 그래프 연결 문제에서 MST 개념이 등장하고, 이를 해결하는 두 대표 탐욕 전략으로 프림과 크루스칼이 분화되는 구조를 보여 준다.

👶 어린이를 위한 3줄 비유 설명

  1. 여러 섬을 다리로 이어야 할 때, 이미 연결된 섬 무리에서 가장 싼 다리 하나만 계속 고르는 게 프림 알고리즘이에요.
  2. 그래서 같은 섬을 빙빙 도는 쓸데없는 다리를 만들지 않고 모두를 이어 갈 수 있어요.
  3. 중요한 것은 우리 집에서 제일 가까운 섬을 찾는 게 아니라, 섬 전체를 가장 적은 돈으로 잇는 거예요.