문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

문제 링크

풀이

N 명의 학생을 탐색하는데 학생들간의 순서를 지키며 탐색해야하는 위상정렬 문제이다.
자신보다 앞에 줄을 서야하는 학생을 부모노드로 둔다.

자신의 모든 부모노드가 탐색되기 전에는 자신이 탐색될 수 없다.
부모로부터 받은 간선의 개수(indegree)를 저장하여 부모노드가 하나씩 탐색될 때마다 indegree의 값을 하나씩 줄인다.
indegree == 0이라면 모든 부모노드가 탐색이 된 것이므로 자신도 탐색이 가능하다.

그래프 탐색은 BFS, DFS 상관없이 가능하다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<int> graph[32001];
vector<int> in_degree(32001, 0);
queue<int> q;
void topological_sort(){
  for(int i=1; i < n+1; i++){
    if(in_degree[i] == 0){
      q.push(i);
    }
  }

  while(!(q.empty())){
    int v = q.front();
    q.pop();
    cout << v << ' ';
    for(int i: graph[v]){
        in_degree[i]--;
        if(in_degree[i] == 0){
          q.push(i);
          }
        }
      }
    }
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  
  for(int i=0; i < m; i++){
    int a, b;
    cin >> a >> b;
    graph[a].emplace_back(b);
    in_degree[b]++;
  }
  topological_sort();
    return 0;
}