위상정렬 (Topological Sort),2252 줄세우기

위상정렬 (Topological Sort)

위상정렬은 순서가 정해져있는 작업을 수행할 때 그 순서를 결정해주기 위해서 사용되는 알고리즘이다.

순서가 정해져있다는 말은 조건이 걸린다고 생각하면 편하다. 어떠한 작업은 어떠한 이전작업들이 수행되야 수행된다라는 순서가 정해져있는 것이다.

 

그림을 생각해야 이해가 편하므로 그림을 보자.

https://blog.naver.com/ndb796/221236874984

각 정점들은 자신을 가르키고 있는 모든 정점들이 수행된 후에 실행될 수 있다. 가르켜 지고있는 수를 차수(degree)라고 하자. 예를들어 정점2는 정점1 하나가 가르키고 있으므로 차수는 1이다.6번은 4,5로 인해 2이고 1번은 0이 될 것이다. 그렇다면 가능한 순서를 임의로 정해보자

1->2->3->4->5->6->7도 가능할 것이고 1->2->3->5->4->6->7 등등 순서만 지키면 가능한 경우가 많을 것이다. 위상정렬의 특징은 여러개의 답이 존재할 수 있다는 것이다.

하지만 여기서 중요한 것은 위상정렬은 DAG(Directed Acyclic Graph) 싸이클이 없는 방향 그래프에서만 가능 하다는 것이다. 싸이클이 생기게 되면 무한으로 돌게되기 때문에 순서를 정할 수 없다.

 

이제 위상정렬 알고리즘을 만드는 순서를 보자. 나는 queue로 구현할 것이다.

한 정점이 수행되려면 자신의 이전에 수행되어야 하는 정점들이 수행되어야 할 것이다. 따라서 정점들을 수행할 때 마다 그 정점에 달려있던 간선들을 제거해주는 것이다. 간선이 제거되면서 어떤 정점이 차수가 줄어들면서 0이 되면 수행가능한 정점이 되는 것이다 그때마다 큐에 넣어준다. 정리해보면

순서

1. 정점과 간선에 대한 그래프를 만들고 각 정점의 차수를 저장한다.

2. 초기 큐를 만들기 위해 모든 정점에서 차수가 0인 것들을 넣는다.

3. for문을 사용하여 정점의 갯수만큼 큐에서 pop한다(정점의 갯수만큼 빼기전에 큐가 빈다면 사이클이 있는 것이다.)

4. pop된 것에 연결되있는 간선을 지우고 지워지는 곳의 차수를 1씩 뺀다. 차수를 1뺏을때 0이라면 큐에 넣어준다.(실행가능해졌다는 뜻이므로)

5. pop되었던 순서대로 출력하면 위상정렬이 완성된다.

나는 차수방법을 사용해서 queue를 이용해서 풀었지만

그래프를 생각해보면 DFS의 역순으로 나열하는 방법으로도 구현할 수 있다.

시간복잡도는 O(V+E)가 된다.

문제에서 예를들어 설명해보겠다.

 

백준 2252 줄세우기 

www.acmicpc.net/problem/2252

1.접근

두 학생의 키를 비교하는 방법을 쓴 것은 정확한 순서가 필요한 것이 아닌 작은 애가 먼저나오고 큰애가 뒤에 나오기만 하면 되므로 위상정렬을 사용해서 대략적인 순서를 잡아주면 된다. 문제에서도 답이 여러 가지인 경우에는 아무거나 출력하라고 한것이 힌트가 된다.

2.풀이

입력에서 주어지는 키작은 ->키큰 아이를 간선으로 만든다. 위상정렬을 사용할 것이므로 가르켜 질때마다 차수도 늘린다. 큐에 차수가0인부분부터 시작해서 하나씩 뽑아가며 답을 출력한다.

3.코드

4.배운점

• 시간복잡도에서 많이 생각해봤는데 2중 for문 같지만 정점만큼돌고 정점에서도 연결된 간선만 돈다.
• 대략적인 순서가 있을 때 위상정렬을 생각하자