위상정렬(Topological Sorting)

위상정렬

정점(Vertex ; V)과 간선(Edge; E) 가 있을 때, 

1) 방향그래프 (Direct)

2) 사이클이 없음. (Acylic)

인 그래프일 때 사용할 수 있다. 

위 2가지를 전제로하는 그래프이며, 이와 같은 그래프를 DAG(Directed Acyclic Graph) 라고 부른다. 

간단하게 말하자면, 스타크래프트에서 건물을 짓는 순서가 정해져 있고, 선행조건으로 지어져야 하는 건물들이 있을 것이다. 선행 건물을 짓고나서 후행건물을 지을 수 있다. 그렇다면 후행건물을 지으려면 어떻게 해야하는가? 라는 문제가 될 것 같다. 

또는 wikipedia에서는 선수과목을 듣고 다음과목을 수강할 수 있는 것으로 볼 수 있다고 되어 있다. 전자와 후자 둘 다 똑같은 말이니 이해할 것 같다. 

방법은 아래 그림에서 설명한다.

 

 

위 그림과 같이 정점 이 1,2,3,4 가 존재 한다. 설명을 위해서 건물이라고 정하고 얘기를 한다. (건물 1,2,3,4)

이를 보면 건물 1번을 지을 때는 다른 건물을 짓지 않더라도 지을 수 있다. 

건물 2,3번은 1번을 짓고 나서 지을 수 있다. (1->2,3)

4번 건물은 2번,3번을 모두 지어야 만들 수 있다. 

그러면 처음 1번 건물을 지었다. 그리고 2번과 3번을 지어야하는데 이때 순서는 중요하지 않다. 다만 1번이 지어져 있다는 사실을 아는 것이 중요하다. 

다음 그림을 보면 

 

 

 

각 건물 위에 선행적으로 지어져야 하는 건물의 수를 초록색상자 안 숫자로 나타내었다. 

1번은 이전에 지어져야 하는 건물이 없으므로 0, 

2번은 이전에 지어져야 하는 건물이 1번건물이 있으므로 1,

3번도 2번과 동일하게 1,

4번은 2번,3번 건물이 지어져야하므로 2 를 저장하고 있다. 

1번을 지었다고 할 시 각 간선(1->k ; 1->2 / 1->3)을 지나며 다음 건물(k)의 지어야하는 건물! 그리고 이전에 지어져야하는 숫자를 -1 감소시킨다. 그 이후 1은 사용되지 않는다. 

 

그러면 위와 같은 그림이 되고 1은 다시 사용되지 않는다. 

이후 같은 과정을 반복한다. 선행적으로 건물을 짓지 않았으며, 이전에 지어져야 하는 건물 수가 0인 것을 찾아 탐색한다. 

 

 

 

그러면 건물 2와 3을 보게 되며, 4번을 짓기 위해서 위의 과정을 반복한다. 

 

 

그리고 더이상 탐색할 건물 다음 테크가 없다면 그만한다. 

순서를 요약하면,

구성된 DAG 구조 그래프에서 

1. 진입 간선이 0인 (자신에게 오는 간선이 없는 것) 정점을 탐색하기 위해서 원하는 자료구조에 모두 넣는다. 

2. 해당 자료구조에서 꺼내며, 해당 정점의 간선을 모두 탐색하며 탐색 시 이동할 수 있는 정점의 진입간선 수를 -1 한다. (감소시킨다.)

3. 감소시킨 정점이 진입간선 수가 0이 되면 1번의 자료구조에 넣는다. 

4. 자료구조의 데이터가 사라질 때까지 과정을 반복한다. 

위와 같은 순서로 난 작성하였다. 

자료구조는 큐를 사용하였으며, 위와 같이 작성하여 백준온라인저지에 1005번 문제를 풀었다. 시간을 어떻게 할 것인지에 관한 것은 1005번 문제를 푼 포스팅을 보면 될 것 같다.

 

http://wondy1128.tistory.com/27