YEAHx4YEAHx4
PS

Topological Sort

위상 정렬

YEAHx4

YEAHx4

2026-02-26
10 mins

Topological Sort

위상 정렬은 이름처럼 정렬의 일종이지만 일반적인 정렬과는 다릅니다. 다른 정렬 알고리즘은 배열에서 원소들의 순서를 바꾸는 방식으로 정렬을 하지만, 위상 정렬은 그래프에서 수행합니다. 예를 들어, 어떤 작업을 수행하기 위해 선행 작업이 있는 경우가 있습니다. 이때 수행할 작업의 순서를 정하는 것이 위상 정렬입니다. 위상 정렬은 방향 그래프에서만 수행할 수 있습니다. 그리고 사이클이 존재하는 그래프에서는 수행할 수 없습니다. 마치 닭과 계란 중 무엇이 먼저인지 알 수 없는 것과 같습니다. 아래 그래프를 봅시다.

graph

이 그래프에서 가장 먼저 수행될 수 있는 작업은 0입니다. 아무 선행 작업이 없기 때문입니다. 그 다음으로 수행될 수 있는 작업은 1 또는 2입니다. 어떤 작업이 진행되기 위한 조건은 그 작업의 선행 작업이 모두 수행되어야 한다는 것입니다. 1과 2는 모두 0이 선행 작업이므로 0이 수행된 후에 수행될 수 있습니다.

이런 방향이 있고 사이클이 없는 그래프를 DAG(Directed Acyclic Graph)라고 합니다. 방향 그래프에서 어떤 노드로 들어오는 간선의 개수를 그 노드의 진입 차수(indegree)라고 합니다. 어떤 노드가 처리되기 위해서는 그 노드의 진입 차수가 0이 되어야 합니다. 위 그래프에서 진입 차수를 나타내 보면 다음과 같습니다

노드0123456
진입 차수0112112

위상 정렬은 다음과 같이 수행됩니다.

  • 진입 차수가 0인 노드를 큐에 넣습니다. 위 그래프에서는 0이 진입 차수가 0이므로 큐에 넣습니다.
  • 큐에서 노드를 하나 꺼냅니다. 꺼낸 노드를 처리합니다.
    • 꺼낸 노드에서 나가는 간선을 모두 제거합니다.
    • 간선을 제거하면 그 간선의 도착 노드의 진입 차수가 1 줄어듭니다.
    • 만약 도착 노드의 진입 차수가 0이 되면 그 노드를 큐에 넣습니다.
  • 큐가 빌 때까지 반복합니다.

BOJ 2252 줄 세우기 문제를 풀어보겠습니다. 키 순서대로 학생을 정렬해야 하는데, 학생들의 키를 아는 것이 아니라 두 학생의 상대적인 비교만 아는 상태입니다. 각 학생을 노드라고 생각하면 두 학생 간 상대적인 비교는 방향이 있는 간선으로 표현할 수 있습니다. 이 상태에서 위상정렬을 수행하면 키 순서대로 학생을 정렬할 수 있습니다. 위상 정렬의 결과는 항상 하나가 아닐 수 있습니다. 위 그래프에서도 0 다음에 1이나 2가 올 수 있었습니다. 이 문제에서는 아무 결과나 출력하면 되기 때문에 크게 걱정하지 않아도 됩니다. 또, 이 문제에서는 그래프가 전부 연결되지 않을 수 있습니다. 이 경우에도 위상 정렬을 문제 없이 수행할 수 있습니다. 진입 차수가 0이지만 서로 다른 그래프에 속한 노드들이 있는 경우에는 아무거나 먼저 처리해도 상관없기 때문에 이것 또한 신경쓰지 않고 처리할 수 있습니다.

우선 입력을 받습니다. 입력을 받을 때 인접 리스트로 그래프를 저장하고, 각 노드의 진입 차수도 저장합니다.

int n, m; cin >> n >> m;
int deg[n + 1];
vector<int> adj[n + 1];
memset(deg, 0, sizeof(deg));

while (m--) {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    deg[v]++;
}

큐에 진입 차수가 0인 노드를 넣습니다.

queue<int> q;
for (int i = 1; i <= n; i++)
    if (deg[i] == 0) q.push(i);

이제 큐가 빌 때까지 하나씩 꺼내오면서 위상 정렬을 수행합니다. 큐에서 꺼낸 노드에서 나가는 간선을 모두 제거하면서 도착 노드의 진입 차수를 1씩 줄입니다. 만약 도착 노드의 진입 차수가 0이 되면 그 노드를 큐에 넣습니다. 위상 정렬의 결과는 큐에서 꺼낸 노드의 순서입니다.

vector<int> ans;
while (!q.empty()) {
    int u = q.front(); q.pop();
    ans.push_back(u);
    for (int v : adj[u]) {
        deg[v]--;
        if (deg[v] == 0) q.push(v);
    }
}

이제 ans 벡터에 위상 정렬의 결과가 저장되어 있습니다. 이 결과를 출력하면 됩니다. 전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

int main() {
    fio();

    int n, m; cin >> n >> m;
    int deg[n + 1];
    vector<int> adj[n + 1];
    memset(deg, 0, sizeof(deg));

    while (m--) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        deg[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0) q.push(i);

    vector<int> ans;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ans.push_back(u);
        for (int v : adj[u]) {
            deg[v]--;
            if (deg[v] == 0) q.push(v);
        }
    }

    for (int x : ans) cout << x << ' ';
}