그래프 알고리즘 중에서도 최소 신장 트리(Minimum Spanning Tree)를 찾는 알고리즘은 네트워크 설계부터 클러스터링까지 다양한 분야에서 활용됩니다. 프림 알고리즘은 이러한 최소 신장 트리를 구하는 대표적인 방법으로, 특히 밀집된 그래프에서 뛰어난 성능을 보여줍니다.
프림 알고리즘 구현
프림 알고리즘은 시작 정점에서부터 단계적으로 트리를 확장해 나가는 방식으로 동작합니다. 매 단계마다 현재 트리와 연결된 간선 중 가장 가중치가 작은 간선을 선택하여 트리에 추가합니다. 이러한 과정을 모든 정점이 트리에 포함될 때까지 반복합니다.
프림 알고리즘의 핵심은 우선순위 큐를 사용하여 현재 트리에서 가장 가중치가 작은 간선을 효율적으로 찾는 것입니다. 이를 통해 시간 복잡도를 최적화할 수 있습니다.
아래 구현에서는 인접 리스트 형태의 그래프를 입력으로 받습니다. 각 정점에 대해 연결된 정점과 그 간선의 가중치를 딕셔너리로 표현합니다. 우선순위 큐를 사용하여 항상 최소 가중치의 간선을 선택하므로, 시간 복잡도는 O(E log V)가 됩니다. 여기서 E는 간선의 수, V는 정점의 수입니다.
프림 알고리즘은 특히 간선이 많은 밀집 그래프에서 크루스칼 알고리즘보다 효율적으로 동작하는 경향이 있습니다. 이는 간선을 정렬하는 과정이 필요 없고, 현재까지 구성된 트리에 연결된 간선만 고려하기 때문입니다.
프림 알고리즘과 크루스칼의 차이점
프림 알고리즘과 크루스칼 알고리즘은 모두 최소 신장 트리를 찾는 알고리즘이지만, 접근 방식과 성능 특성에 있어 중요한 차이점을 가지고 있습니다. 이러한 차이점을 이해하면 문제 상황에 따라 적절한 알고리즘을 선택할 수 있습니다.
동작 원리의 차이
프림 알고리즘은 하나의 시작 정점에서 출발하여 트리를 점진적으로 확장해 나가는 방식입니다. 매 단계마다 현재 트리와 연결된 간선 중 가장 가중치가 작은 간선을 선택하여 트리에 추가합니다. 즉, 항상 연결된 트리를 유지하면서 확장해 나갑니다.
반면, 크루스칼 알고리즘은 그래프의 모든 간선을 가중치 기준으로 정렬한 후, 가장 가중치가 작은 간선부터 순차적으로 선택합니다. 이때 사이클을 형성하지 않는 간선만을 선택하여 최소 신장 트리를 구성합니다. 크루스칼 알고리즘은 선택된 간선들이 처음에는 서로 분리된 여러 부분 트리를 형성할 수 있으며, 알고리즘이 진행됨에 따라 이들이 점차 하나의 트리로 합쳐집니다.
구현 방식의 차이
프림 알고리즘은 주로 우선순위 큐를 활용하여 구현되며, 현재 트리에 인접한 간선들 중 최소 가중치를 가진 간선을 효율적으로 찾습니다. 방문한 정점을 추적하기 위해 집합(set)을 사용합니다.
크루스칼 알고리즘은 간선들을 가중치 기준으로 정렬한 후, 유니온-파인드(Union-Find) 자료구조를 사용하여 사이클 여부를 검사합니다. 이 자료구조는 두 정점이 같은 집합(또는 부분 트리)에 속하는지 빠르게 확인할 수 있게 해 줍니다. 아니면 정점이 연결되었는지 아닌지로 간단히 체크해 줄 수 있습니다. 이 부분은 아래 코드에 구현되어 있습니다.
성능 특성의 차이
시간 복잡도 측면에서, 프림 알고리즘은 우선순위 큐를 사용할 경우 O(E log V)의 시간 복잡도를 가집니다. 크루스칼 알고리즘은 간선 정렬에 O(E log E) 시간이 소요되며, 유니온-파인드 연산은 거의 상수 시간에 가까워 전체적으로 O(E log E) 또는 O(E log V)의 시간 복잡도를 가집니다.
그래프 특성에 따른 선택: 프림 알고리즘은 간선이 많은 밀집 그래프(dense graph)에서 더 효율적인 반면, 크루스칼 알고리즘은 간선이 적은 희소 그래프(sparse graph)에서 더 효율적인 경향이 있습니다. 이는 프림 알고리즘이 정점 중심으로 동작하고, 크루스칼 알고리즘이 간선 중심으로 동작하기 때문입니다.
프림 알고리즘을 사용하는 코딩테스트 문제
프림과 크루스칼 모두 MST를 구현하기 위한 방법입니다. 그래서 대부분의 경우 어떤 알고리즘을 사용해도 상관없습니다. 어떤 정점이 연결되느냐가 달라질 뿐 최종적으로 MST가 만들어지기 때문이죠. 하지만 문제에서 프림으로 작성하는 것을 간접적으로 요구하는 경우가 있습니다. 아래와 같은 문제를 생각해 봅시다.
문제 예시: 실시간 네트워크 구축
문제 설명:
여러분은 컴퓨터 바이러스를 만들었습니다. 여러분의 목적은 N개의 컴퓨터를 전부 감염시키는 것입니다. 각 컴퓨터는 (x, y) 좌표에 위치해 있으며, 두 컴퓨터 간의 이동 비용은 두 점 사이의 유클리드 거리입니다. 여러분은 1번 컴퓨터를 감염시켰으며, 매 순간 최소 비용으로 이동할 수 있는 컴퓨터를 찾아 해당 컴퓨터를 감염시킵니다. 최종적으로 모든 컴퓨터가 감염되었을 때의 최소 비용을 구하세요.
입력:
첫 번째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1,000)
다음 N개의 줄에 각 컴퓨터의 x, y 좌표 (-1,000 ≤ x, y ≤ 1,000)
해결 방법:
문제에서 직접 언급하지는 않았지만 사실 프림으로 해결하라고 말을 한 셈입니다. 왜냐하면:
- 1번 컴퓨터에서 시작해야 한다는 제약 조건이 있습니다.
- 매 순간 "현재 감염된 컴퓨터"와의 거리를 고려해야 합니다.
- 간선이 명시적으로 주어지지 않고, 필요할 때마다 계산해야 합니다.
크루스칼 알고리즘은 모든 간선을 미리 정렬해야 하므로, 동적으로 가장 가까운 정점을 찾는 이런 문제에는 적합하지 않습니다.
이 문제는 프림 알고리즘의 특성을 잘 활용한 예입니다. 매 단계에서 이미 구축된 네트워크에서 가장 가까운 컴퓨터를 선택해야 하기 때문에, 정점 중심으로 동작하는 프림 알고리즘이 자연스러운 해결책이 됩니다.
이런 식으로 문제가 출제될 수도 있기 때문에 프림과 크루스칼 모두 잘 알아두어야 합니다.
최소 신장 트리를 구하는 프림 알고리즘은 그래프 이론에서 가장 기본적이면서도 강력한 도구 중 하나입니다. 특히 정점 중심의 접근 방식과 동적인 확장 특성은 많은 실전 문제에서 유용하게 활용될 수 있습니다. 알고리즘의 동작 원리와 구현 방법을 제대로 이해하고, 적절한 상황에 적용한다면 효율적인 솔루션을 구축할 수 있을 것입니다.