위상 정렬

위상 정렬

위상 정렬은 방향 비순환 그래프에서 어떠한 노드가 탐색되려면 그 이전 노드가 모두 탐색되어야 할 때 탐색하는 순서를 알 수 있는 알고리즘입니다. 예를 들어 다음과 같은 상황에서 사용할 수 있습니다.

E과목을 수강하기 위해 C과목, C과목을 수강하기 위해 A, B, D과목, D과목을 수강하기 위해 B과목을 수강해야한다면 다음과 같이 그래프로 나타낼 수 있습니다.

이때 순서는 A → B → D → C → E 라고 할 수 있습니다. 혹은 B → D → A → C → E 일수도 있습니다. 그러나, D를 먼저 시작하거나, C를 먼저 시작할 수는 없습니다. 왜냐하면 이전에 수강해야하는 과목이 있기 때문입니다. 즉, 자기 쪽으로 들어오는 그래프가 있다면 그것은 시작할 수 없습니다. 따라서, 위상 정렬에서는 진입차수(In degree)의 개념을 사용합니다.

위상 정렬의 동작 원리

위상 정렬은 BFS처럼 queue를 사용합니다. 그러나 BFS와 달리, 들어오는 그래프가 없어야하므로, 진입차수가 0인 노드만 queue에 추가합니다. 그리고 탐색을 하면서, 연결된 노드의 진입차수를 1씩 줄여줍니다. 이때, 연결된 노드의 진입차수가 0이 되었다면 queue에 추가합니다.

위의 그래프에서 위상 정렬을 사용하면 다음과 같습니다.

node	A	B	C	D	E
in	0	0	3	1	1

위는 진입차수를 나타낸 것입니다. 여기서, 진입차수가 0인 노드는 A와 B입니다. 따라서 A와 B를 queue에 추가해줍니다.

Step #1

queue에서 A를 pop하고 A와 연결된 노드의 진입차수를 1 낮춰줍니다. 이때, 그 노드의 진입차수가 0이라면 queue에 추가하지만, 아니라면 추가하지 않습니다. 따라서 진입차수는 다음과 같습니다.

node	A	B	C	D	E
in	0	0	2	1	1

Sequence는 다음과 같습니다.

A

Step #2

queue에서 B를 pop하고 B와 연결된 노드의 진입차수를 1 낮춰줍니다. 이때 D의 진입차수가 0이 되었으므로 queue에 삽입합니다.

node	A	B	C	D	E
in	0	0	1	0	1

Sequence :

A	B

Step #3

queue에서 D를 pop하고 연결된 노드의 진입차수를 1 낮춰줍니다. 이때 C의 진입차수가 0이 되었으므로 queue에 삽입합니다.

node	A	B	C	D	E
in	0	0	0	0	1

Sequence :

A	B	D

Step #4

queue에서 C를 pop하고 연결된 노드의 진입차수를 1 낮춰줍니다. 이때 E의 진입차수가 0이 되었으므로 queue에 삽입합니다.

node	A	B	C	D	E
in	0	0	0	0	0

Sequence :

A	B	D	C

Step #5

마지막으로 E를 pop했으나, 이제 연결된 요소가 없으므로 종료합니다.

Sequence :

A	B	D	C	E

이런식으로 위상 정렬 알고리즘을 사용해 탐색 순서를 파악할 수 있습니다.

주의할 점

위상 정렬 알고리즘의 시간복잡도는 모든 정점과 간선을 한번씩 탐색하므로 $O(V + E)$입니다.

위상 정렬 알고리즘은 순환 그래프에서는 사용할 수 없습니다. 왜냐하면, 진입차수가 1 이상인 사이클이 존재하기 때문입니다.

Python 코드(BOJ 2252)

import sys
from collections import deque

sys = sys.stdin.readline
n, m = map(int, input().split())
in_degree = [0] * n
table = {}
for _ in range(m):
    x, y = map(int, input().split())
    in_degree[y-1] += 1
    if x not in table:
        table[x] = [y]
    else:
        table[x].append(y)

queue = deque([i+1 for i in range(n) if in_degree[i] == 0])
while queue:
    x = queue.popleft()
    print(x, end=' ')
    if x in table:
        for i in table[x]:
            in_degree[i-1] -= 1
            if in_degree[i-1] == 0:
                queue.append(i)