우선순위 큐를 이용한 위상정렬

Computer/Algorithms 2007/04/16 21:08

위상정렬이란?

위상정렬은 일의 순서를 정하는 것이라고 요약할 수 있다. 스타크래프트를 생각하면 쉬워진다. 스타크래프트에서, 마린을 생산하기 위해서는 배럭스가 필요하고, 배럭스를 짓기 위해서는 먼저 SCV가 있어야 한다. 즉 마린을 배럭스보다 먼저 생산할 수는 없으며, SCV 없이 배럭스를 지을 수 없다는 것이다. 이와 같이 어떤 일을 하기 위해서 꼭 선행되어야 하는 일이 정해져있을 때, 모든 일을 하기 위한 일의 순서를 정하는 것이 위상정렬이다.

우선순위 큐란?

우선순위 큐는 힙을 이용하는 자료구조이다. 힙이란, 자료의 삽입/삭제시에 모든 자료의 정렬이 자동으로 이루어지는 구조이다. 힙은 기본적으로 이진 트리의 구조인데, Parent, Left, Right가 있을 때 항상 Parent가 제일 크다는 전제 하에 이루어지는 트리이다. STL에서는 우선순위 큐를 제공하므로 이를 사용하면 편리하게 프로그래밍을 할 수 있다.
위상정렬을 할 때 원래는 그냥 큐를 사용해도 무방하나, 각 일에 번호가 매겨져있고, 가능하다면 작은 번호가 선행되도록 하고 싶다면 우선순위 큐를 사용하여야 한다. 우선순위 큐는 한 번의 삽입, 삭제시에 lgN의 시간이 소요되기 때문에 큰 부담 없이 사용할 수 있다.

우선순위 큐를 이용한 위상정렬의 방법

1. 모든 일의 선행 필요조건 관계를 따라 그래프를 그린다. (W1을 해야 W2를 할 수 있는 경우 W1에서 W2로 간선을 그린다. 이와 같이 하면 방향성 그래프가 완성된다.)
2. 각 일에 대해 Indegree를 센다. (Indegree = 내차수 = 자신으로 들어오는 간선의 개수)
3. Indegree가 0인 일을 모두 찾아 우선순위 큐에 넣는다.
4. 우선순위 큐에서 일 하나를 꺼낸다.(위상정렬의 결과를 출력하고 싶다면 이 때 꺼내진 일을 출력하면 된다.)
5. 방금 꺼낸 일에 연결된 모든 일들의 Indegree를 1씩 감소시킨다.
6. Indegree가 감소된 일들 중 Indegree가 0인 일이 있으면 우선순위 큐에 넣어준다.
7. 우선순위 큐가 빌 때까지 4~6을 반복한다.