MST 문제, 그리고 우선순위 큐

Priority queue도 은근히 알고 있으면 좋은 자료구조/알고리즘이다. 사실상 heapSort를 써야 하는 자리일 때 요긴하게 쓰는데… 보통 최솟값/최댓값”만"을 효율적으로 뽑아내고 싶을때 사용한다.

그렇다면 어디에 쓸 수 있을까? 사실 쓸 수 있는 곳은 무지막지하게 많다.

• 그저께 썼던 “Merge K lists” 문제
• push/pop/min/max 쿼리를 처리하는 프로그램 짜기
  • 간단히 설명하면, push/pop 할 때 heap을 갱신해주면 된다. heap 조회는 O(k), heap 갱신은 O(klogn) 인데, heap 없이 매번 검색을 수행하면 조회에 소요되는 시간 복잡도가 커서 (O(kn) ?) 시간 복잡도에서 나쁘다.
• MST(최소 신장 트리) 문제
• 등등

그 중 MST 문제의 Prim 알고리즘에서 priority queue가 쓰인다. 처음 해답을 보고 꽤 감탄했던 기억이 있는데, 그 때 기억을 되살려서 한번 다시 정리 해보는 걸로 …

MST 문제의 유형

먼저 MST 문제가 2 가지가 있음을 짚고 넘어가보자.

• 크루스칼: 간선을 추가하는 방식으로 MST 구성
• 프림: 노드를 추가하는 방식으로 MST 구성

크루스칼은 비교적 간단하다. 적은 가중치의 간선부터 추가하면 되는데, 따라서 간선을 sorting 하고 훑는 것으로 끝이다. 따라서 시간복잡도는 O(E log E) 로 자명하다. 물론 cycled 되지 않게 신경 써줘야 함

프림은 노드를 추가해나가며 그래프를 만드는 방식인데, 크루스칼처럼 정해진 순서대로 편하게 집어넣을 수는 없고, 현재 노드들과 인접해있는 간선을 추가해 가면서 노드를 추가해 나가게 된다.

그렇다면 결국? 최소 간선을 추가해나가는 방식으로 알고리즘을 만들어야 하는데, 매번 간선 목록이 갱신될 때마다(= 노드 추가할 때마다) sort 수행/fullscan 하는건 매우 큰 부담이고, O(V^2) 또는 O(VElogE)(?) 만큼의 시간이 걸린다.

이 때 priority queue를 이용하여 edge를 관리한다면 훨씬 수월해진다.

1. node를 추가할때마다 인접한 edge들을 pqueue에 넣고,
2. pqueue에서 edge를 꺼내서, 아직 포함되지 않고 && 인접하지 않은 node에 걸치는지 확인한 후
3. 맞다면 노드 추가하고 (1)로 돌아가기.

이 과정을 V 번 반복하고, heap sort는 O(logE) 이므로 총 O(VlogE) 가 된다.

이제 어떤 알고리즘을 어디에 써야 하는지가 남은 관건이다. 당연하지만, edge의 개수가 많다면(full density), 프림을 선택하는게 훨씬 낫고, node가 많다면 (sparse graph) 크루스칼을 쓰는 쪽이 효율적이다.

이미지 출처: Wikipedia

TMI: 알고리즘 경시대회의 꽃은 그래프 문제인 것 같다. 근데 실무에는 별 도움 안되는 이상한 이론들(유량문제, 외곽선 문제 등) 많이 공부해야 함... ㅋㅋ. 그래서 아마 여기서는 굳이 안 다루지 않을까.