위상 정렬 (Topology Sort)

위상 정렬(Topology Sort)

유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 기법
(순서가 있는 작업들에 순서에 맞게 배치해주는 기법)

예시) 하루 일과 작업 순서 정하기

가능한 일의 순서
1 -> 2 -> 3 -> 5 -> 4 -> 6 -> 7
1 -> 2 -> 5 -> 4 -> 3 -> 6 -> 7
…
1 -> 5 -> 2 -> 6 -> 7 -> 4 -> 3

구현 방법

1. 유향 그래프를 생성하는 동시에 선행 작업의 차수를 저장한다.
2. Queue를 통해 작업의 우선 순위를 관리한다.
   • 선행 작업이 필요없는 작업부터 큐에 삽입한다.
   • 큐에서 요소를 하나씩 제거하며 제거하는 작업 이후에 시행되는 작업의 차수를 감소시킨다.
   • 차수가 0이 된 작업은 큐에 삽입한다.

Sample 코드 (boj 2252 - 줄 세우기)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
int degree[32010];
vector<int> G[32010];

void topologySort() {
  queue<int> q;
  for(int i=1; i<=n; i++)
    if(!degree[i])
      q.push(i);
  while (!q.empty()) {
    int cur = q.front();
    cout << cur << ' ';
    q.pop();
    for(int nxt : G[cur]) {
      if(--degree[nxt] == 0) q.push(nxt);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for(int i=0; i<m; i++) {
    int u,v; cin >> u >> v;
    G[u].push_back(v);
    degree[v]++;
  }
  topologySort();
}