최소 신장 트리 MST: 크루스칼과 프림 알고리즘 완벽 비교
여러 도시를 연결하는 도로망을 설계하거나 광통신망을 구축할 때, 우리는 '모든 정점을 연결하되 전체 길이는 최소화'해야 하는 최적화 문제에 직면합니다. 이를 그래프 이론에서는 최소 신장 트리(Minimum Spanning Tree, MST)라고 부릅니다. MST를 구현하는 가장 대표적인 두 알고리즘인 크루스칼(Kruskal)과 프림(Prim)은 모두 그리디(Greedy) 기법을 사용하지만, 문제를 바라보는 관점이 완전히 다릅니다. 본 포스팅에서는 두 알고리즘의 매커니즘 차이와 상황별 최적의 선택 기준을 2,500자 이상의 상세한 분석으로 정리해 보겠습니다.
1. 크루스칼(Kruskal) 알고리즘: 간선 중심의 그리디 전략
크루스칼 알고리즘은 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한 뒤, 가장 작은 간선부터 순차적으로 트리에 포함시키는 방식입니다. 이 과정에서 사이클(Cycle)이 발생하는지 여부를 판별하는 것이 핵심이며, 이를 위해 유니온 파인드(Union-Find) 자료구조를 필수적으로 활용합니다. 간선 위주로 정렬하여 탐색하므로, 간선의 개수가 적은 희소 그래프(Sparse Graph) 환경에서 매우 강력한 성능을 발휘합니다.
1-1. 크루스칼의 시간 복잡도와 정렬의 역할
크루스칼의 전체 시간 복잡도는 간선을 정렬하는 데 가장 많은 시간이 소요되어 $O(E \log E)$가 됩니다. 유니온 파인드 연산은 거의 상수에 가깝기 때문에 무시할 수 있을 정도입니다. 따라서 간선 $E$가 적을수록 이 알고리즘은 압도적인 효율성을 보여줍니다.
2. 프림(Prim) 알고리즘: 정점 중심의 그리디 전략
프림 알고리즘은 하나의 시작 정점에서 출발하여, 현재 트리에 포함된 정점들과 연결된 간선 중 가장 가중치가 작은 간선을 선택하며 트리를 확장해 나가는 방식입니다. 다익스트라 알고리즘과 매우 유사한 구조를 가지며, 매 단계에서 최소 가중치 간선을 빠르게 찾기 위해 우선순위 큐(Priority Queue)를 사용합니다. 정점 위주로 확장해 나가므로, 간선이 빽빽하게 들어찬 밀집 그래프(Dense Graph)에서 크루스칼보다 유리한 경향이 있습니다.
2-1. 프림의 성능과 데이터 구조의 중요성
우선순위 큐를 적용한 프림 알고리즘의 복잡도는 $O(E \log V)$입니다. 정점의 개수 $V$에 비해 간선의 개수 $E$가 기하급수적으로 많아질 때, 프림은 간선을 정렬해야 하는 크루스칼보다 유리한 고지를 점하게 됩니다.
3. 크루스칼 vs 프림: 어떤 알고리즘을 선택할 것인가?
두 알고리즘의 선택은 결국 그래프의 밀집도에 달려 있습니다. 정점의 개수 대비 간선의 개수가 적다면 구현이 단순하고 간선 정렬이 빠른 크루스칼이 좋으며, 간선이 매우 많아 정렬 비용이 크다면 프림이 더 적절합니다. 실제 코딩 테스트나 실무 설계 시에는 문제에서 주어지는 $V$와 $E$의 범위를 분석하여 시간 제한 내에 동작할 수 있는 알고리즘을 선별하는 안목이 필요합니다.
실무적인 응용 분야
- 통신 네트워크 설계: 최소 비용으로 모든 지역을 연결하는 광케이블 배선 최적화.
- 수도 및 가스관 설치: 관로의 총 길이를 최소화하여 설치 비용 절감.
- 클러스터링(Clustering): 데이터 분석에서 비슷한 특징을 가진 그룹을 최소 비용 기반으로 묶는 작업.
1. 크루스칼: 간선 중심 알고리즘으로, 유니온 파인드를 사용하며 희소 그래프에 적합합니다.
2. 프림: 정점 중심 알고리즘으로, 우선순위 큐를 사용하며 밀집 그래프에 적합합니다.
3. 공통점: 두 방식 모두 그리디 전략을 취하며, 사이클 없는 최소 비용의 전역 연결을 보장합니다.