정렬 알고리즘 : 위상 정렬 (Topological Sorting)

방향이 있는 그래프의 정점들을 방향대로 나열하는 것

 

위상 정렬의 예시

 

예시를 위해 자랑스러운 나의 전공, 국문학과의 국어학 커리큘럼을 가져와보았다. 보통 'OO론' 과목은 'OOO의이해' 수업을 선수과목으로 하여, 순서상 '이해' 과목을 먼저 들어야 한다. 그리고 제일 마지막은 역시.. 대학원 수업인 'OOO연구'.

'국어학의이해'를 듣지 않고 '국어형태론'을 먼저 수강했다간 큰 코 다칠 수가 있다.

 

위상정렬을 사용하면 올바른 수강 순서를 찾을 수 있다.

 

 

DAG(Directed Acyclic Graph)

위상 정렬은 사이클이 존재하지 않는 유향 그래프에 적용할 수 있다. 사이클이 존재한다면 출발점을 알 수 없기 때문에 위상 정렬이 불가능.

 

 

진입차수 & 진출차수

위상 정렬을 위한 '진입차수'와 '진출차수'의 개념을 먼저 짚어보자.

 

- 진입차수(Indegree) : 어떤 노드로 들어오는 간선의 개수

- 진출차수(Outdegree) : 어떤 노드로 나가는 간선의 개수

 

동작 과정

큐를 사용하는 방법

큐를 사용하면 BFS 방식이며, '진입차수'를 사용한다고 보면 된다.

 

- 진입차수가 0인 정점을 큐에 넣는다

- 큐에서 노드를 꺼내서 연결된 모든 간선을 제거한다

- 진입차수가 0이 된 정점을 큐에 넣는다

- 큐가 빌 때까지 위 과정을 반복한다

--> 큐에서 꺼낸 순서가 위상 정렬의 결과가 된다

 

*모든 정점을 방문하기 전에 큐가 빈다? 사이클이 존재한다는 의미.

(=큐에 넣을 수 없는 정점이 발생한다)

 

위에서 예시로 들었던 커리큘럼을 그래프 형태로 정리하고, 각 노드의 진입차수를 표로 나타냈다.

 

 

먼저 진입차수가 0인 A를 큐에 넣어주었다. 그 다음 큐에서 A를 꺼내면서 연결된 간선들을 제거한다.

진입차수가 0이 된 B, C, D 를 큐에 넣는다.

 

같은 방식으로 B, C, D 를 큐에서 꺼내다보면 진입차수가 0이 된 E를 마지막으로 꺼내게 된다.

참고로, 위상 정렬은 답이 여러 개가 될 수가 있다!

 

*만약에 싸이클이 존재하는 그래프였다면?

 

노드 E에서 노드B로 가는 간선을 추가해서 사이클을 만들어보았다.

그리고 같은 방식으로 큐에 넣고 간선을 제거하기를 반복하다보면, 어느 순간 사이클에 포함된 원소들이 큐에 들어가지 못하는 상황이 발생한다 (진입경로가 0이 되지 않으므로)

결국에 정점 B, E를 방문하지 못한 채 큐가 비게 되므로 사이클이 존재한다고 판단할 수 있다.

 

스택을 사용하는 방법

스택을 사용한다면 DFS 재귀 방식으로 구현할 수 있으며, '진출차수'를 이용하게 된다.

 

- 처음부터 순회를 하면서 Boolean으로 순회 여부를 체크한다

- 각 정점을 순회하면서, 재귀를 통해 정점이 가리키는 정점을 순회한다

- 더이상 가리키는 정점이 없으면 현재 정점부터 차례로 스택에 넣는다

- 스택에서 하나씩 pop한다

 

 

먼저 임의의 정점 A에서 DFS를 실시한다. 진출차수가 없는 E까지 깊숙히 들어간 다음 스택에 넣는다. 이 과정을 반복하다보면 스택의 마지막에 정점 A가 들어간다.

스택에서 차례대로 pop하면 된다.

 

정리하면,

- 큐로 구현한 위상 정렬 -> 진입차수 활용한 BFS -> 들어오는 게 없는 정점들을 큐에 담아주며 넓게 탐색한다

- 스택으로 구현한 위상 정렬 -> 진출차수 활용한 DFS -> 더이상 정점이 뻗어나가지 못하는 곳까지 깊숙히 들어가 탐색한다

 

시간복잡도

모든 노드와 간선을 확인한다는 점에서 $O(V+E)$의 시간복잡도가 소요된다.

 

 

예제

백준 2252번 줄 세우기 문제를 통해 파이썬 코드를 알아보자.

https://woo-niverse.tistory.com/238

[백준/약점체크] 2252번: 줄 세우기