프림 알고리즘

한 줄 정의: 임의의 한 점에서 출발해 이미 연결된 부분과 가장 값싸게 이어지는 간선을 하나씩 골라 붙여나가며, 모든 점을 최소 비용으로 연결하는 나무(최소신장트리)를 만드는 알고리즘입니다.

쉽게 풀면

여러 마을에 도로를 놓아 전부 연결하되 총 도로 길이를 최소로 하고 싶다고 해봅시다. 프림 알고리즘은 아무 마을에서나 하나 골라 시작한 뒤, "지금까지 연결된 마을들"에서 아직 연결 안 된 마을로 가는 길 중 가장 짧은 길을 매번 하나씩 골라 추가합니다. 이 과정을 모든 마을이 연결될 때까지 반복하면, 전체를 잇는 도로 중 가장 짧은 조합(최소신장트리)이 완성됩니다. 매 순간 "지금 당장 가장 싼 선택"만 하는데도 전체적으로 최적의 결과가 나온다는 점이 특징입니다.

왜 중요한가

프림 알고리즘은 그래프 이론에서 최소신장트리 문제를 푸는 대표적인 탐욕(greedy) 알고리즘으로, 네트워크 설계, 회로 배선, 클러스터링처럼 "여러 지점을 최소 비용으로 연결한다"는 문제 형태가 반복적으로 등장하는 컴퓨터공학·통신공학 논문에서 기본 도구로 널리 쓰입니다. 또한 매 단계의 국소적으로 최선인 선택이 전역적으로 최적인 결과로 이어진다는 점에서, 탐욕 알고리즘의 정당성을 설명하는 대표 사례로도 자주 인용됩니다.

논문에서는 이렇게 쓰입니다

"센서 네트워크의 통신 비용을 최소화하기 위해 프림 알고리즘을 이용해 최소신장트리 기반 토폴로지를 구성하였다."

이 문장은 "여러 노드(장치)를 연결할 때 전체 연결 비용이 가장 적게 드는 구조를 프림 알고리즘으로 찾아냈다"는 뜻입니다. 네트워크 설계, 클러스터링, 회로 배선 등 "여러 지점을 최소 비용으로 모두 연결"하는 문제에 널리 쓰입니다.

"전력망 설계 문제에서 변전소 간 송전선로 배치를 프림 알고리즘 기반으로 최적화하여 총 건설 비용을 줄였다."

이 문장은 전력공학 분야에서 여러 시설을 연결하는 인프라를 설계할 때도 최소신장트리 개념이 비용 절감의 근거로 쓰인다는 것을 보여줍니다.

"계층적 군집분석에 앞서 데이터 포인트 간 유사도 그래프에 프림 알고리즘을 적용해 초기 트리 구조를 생성하였다."

이 문장은 프림 알고리즘이 순수한 그래프 문제뿐 아니라 데이터 분석의 전처리 단계에서도 활용될 수 있음을 보여줍니다.

조금 더 깊게 보면

프림 알고리즘의 성능은 어떤 자료구조로 "다음으로 가장 싼 간선"을 찾느냐에 따라 달라지며, 우선순위 큐(주로 이진 힙)를 사용하면 일반적으로 크루스칼 알고리즘과 비슷하거나 더 나은 시간복잡도를 얻을 수 있습니다. 다익스트라 최단경로 알고리즘과 구조가 매우 비슷해 자주 함께 비교되는데, 다익스트라는 "출발점으로부터의 누적 거리"를 기준으로 다음 노드를 고르는 반면 프림은 "현재 연결된 트리로부터의 간선 비용"만을 기준으로 삼는다는 차이가 있습니다.

주의할 점

같은 최소신장트리를 구하는 크루스칼 알고리즘과 자주 비교되는데, 크루스칼은 간선을 비용 순으로 정렬한 뒤 사이클이 안 생기게 골라 나가는 방식이고, 프림은 "연결된 덩어리"를 점점 넓혀가는 방식이라는 차이가 있습니다. 간선이 매우 많고 촘촘한 그래프에서는 프림 알고리즘이, 간선이 성긴 그래프에서는 크루스칼 알고리즘이 더 효율적인 경향이 있습니다.