[알고리즘] 위상 정렬

아래 글은 'Introduction to Algorithms(한빛아카데미)'와 위상 정렬 개념 및 구현를 보고 작성한 것이다.

대표 문제

• 백준 2252번: 줄 세우기

위상 정렬(Topological Sort)

위상 정렬을 알기 위해서는 먼저 '방향 비순환 그래프(DAG)'에 대해 알고있어야 한다.

방향 비순환 그래프(Directed Acyclic Graph): DAG는 말 그대로, 사이클이 없는 방향 그래프이다. DAG는 보통 이벤트/객체 간의 우선순위를 나타내기 위해 사용된다.

DAG인 그래프 G = (V, E)의 위상 정렬은 G가 간선 (u, v)를 가질 때, u가 v보다 순서상으로 먼저 나타나도록 모든 노드를 선형으로 나열하는 것이다. 즉, 우선순위에 따라 배열을 정렬하는 것이다. 따라서 우선순위 사이에 순환이 있어서는 안된다. 그래프가 순환을 가진다면 우선순위를 매기는 것은 불가능하다. 즉, 그래프가 DAG가 아닌 경우 위상 정렬이 불가능하다.

그래프의 위상 정렬은 모든 방향 간선이 왼쪽에서 오른쪽으로 향할 수 있도록 수평선을 따르는 정점의 나열이라고 볼 수 있다. 그러므로 위상 정렬은 통상적인 정렬과는 다르다.

위상 정렬 과정

BFS 방식

BFS 방식은 in degree가 필요하다.

1. in degree(들어오는 간선의 개수)가 0인 노드를 queue에 넣는다.
2. queue에서 노드를 꺼내서 노드가 가리키는 다음 노드의 in degree를 1 감소시킨다.
3. BFS로 2의 과정을 반복한다. 노드를 꺼낼 때마다 result 리스트에 순서대로 넣는다.
4. 위상 정렬된 리스트 result를 반환한다.

DFS 방식

DFS 방식은 in degree가 필요없다. 대신 재귀를 사용한다.

1. 모든 정점을 순회하며 방문하지 않은 노드에 대해 DFS를 수행한다.
2. 방문표시를 하면서 간선을 따라 다음 노드를 방문한다.
3. 더이상 방문할 노드가 없으면 result 리스트에 노드를 추가한다.
4. 백트래킹을 통해 이전 노드로 이동하면서 방문하지 않은 노드를 확인한다.
5. 방문 가능한 정점이 있다면 다시 간선을 따라 다음 노드로 이동한다.
6. 모든 정점을 탐색할 때까지 2~5번 과정을 반복한다.

위상 정렬의 시간복잡도

깊이 우선 탐색(DFS)는 theta(V + E) 시간이 걸리고 리스트 앞쪽에 |V|개의 정점을 각각 삽입할 때 O(1) 시간이 걸리므로, 위상 정렬은 theta(V + E) 시간에 수행할 수 있다.