[알고리즘] 위상 정렬

위상 정렬은 정렬 알고리즘의 일종이지만, 일반적인 정렬들과는 조금 다르다. 위상 정렬은 순서가 정해진 것들을 나열해야할 때 사용할 수 있는 정렬이기 때문이다. 위키 백과의 설명을 보면 아래와 같다.

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. (출처: 위키 백과)

정의만 보면 쉽게 이해가 가지 않기 때문에 예시를 통해 이해해보도록 하자.

예를 들어 총 5명의 학생이 있는데 학생들을 키의 오름차순으로 정렬하려고 하는 상황이다. 이 때 각 학생들의 실제 키는 모른다. 그리고 학생들의 키 관계는 다음과 같다.

• 1번 학생은 2번, 3번, 4번, 5번 학생보다 키가 크다.
• 2번 학생은 5번 학생보다 키가 크다.
• 3번 학생은 2번, 5번 학생보다 키가 크다.
• 4번 학생은 2번, 3번, 5번 학생보다 키가 크다.
• 5번 학생보다 작은 학생은 없다.

학생 수가 작기 때문에 정답이 5, 2, 3, 4, 1이 되는 것을 쉽게 알 수 있을 것이다. 코드로는 어떻게 정답을 알아낼 수 있을까?
위상 정렬을 하기 위해서 유향 그래프로 관계를 표현해야한다. 키가 작은 학생에서 키가 큰 학생 방향으로 간선이 생기도록 그래프로 표현하면 다음과 같다.

그림을 보면 진입 차수(정점으로 들어오는 간선의 개수)가 적은 순서대로 정답이 나온다는 것을 알 수 있다. 이 점을 이용해서 위상 정렬을 구현할 수 있다. 위상 정렬의 알고리즘은 다음과 같다.

1. 진입 차수가 0인 정점을 큐에 넣는다.
2. 큐에서 꺼내진 정점에서 출발하는 간선을 그래프에서 제거한다.
3. 지운 간선의 도착 정점의 진입 차수를 1 감소시킨다.
4. 1번부터 다시 반복한다.

이해하기 쉽게 그림으로 자세히 알아보자.

진입 차수가 0인 정점을 큐에 집어넣는다. 위 그림에서는 5가 큐에 들어간다.

5에서 출발하는 간선들을 제거한다. 그리고 새롭게 진입 차수가 0이 된 정점 2가 큐에 들어간다.

2에서 출발하는 간선들을 제거하고 새롭게 진입 차수가 0이 된 정점 3이 큐에 들어간다.

3에서 출발하는 간선들을 제거하고 새롭게 진입 차수가 0이 된 정점 4이 큐에 들어간다.

4에서 출발하는 간선들을 제거하고 새롭게 진입 차수가 0이 된 정점 1이 큐에 들어간다.

더 이상 큐에 넣을 정점이 없기 때문에 정렬이 끝난다.

위상 정렬을 코드로 표현하면 아래와 같다.

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int adj[101][101];
int in_degree[101];

void topological_sort() {
    queue<int> q;

    // 진입 차수가 0인 정점을 큐에 넣는다.
    for (int i = 1; i <= n; i++)
        if (in_degree[i] == 0)
            q.push(i);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cout << cur << ' ';

        for (int i = 1; i <= n; i++) {
            // 현재 위치에서 출발하는 간선이 있는 경우
            if (adj[cur][i]) {
                // 도착 정점의 진입 차수를 1 감소시킨다
                in_degree[i]--;
                // 진입 차수가 0인 정점을 큐에 넣는다.
                if (in_degree[i] == 0) {
                    q.push(i);
                }
            }
        }
    }
    cout << '\n';
}

int main() {
    // n은 정점의 개수
    // m은 정점간의 관계의 개수
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        // a에서 b로 가는 간선이 있다
        adj[a][b] = true;
        // b의 진입 차수를 증가시킨다
        in_degree[b]++;
    }
    topological_sort();
    return 0;
}

/*
입력
5 10
2 1
3 1
4 1
5 1
5 2
2 3
5 3
2 4
3 4
5 4

출력
5 2 3 4 1
*/