문제 출처

1. 문제설명

  • 일부 학생들의 키를 비교한 결과가 주어졌을 때 줄을 세우는 순서를 구하라

  • 입력은 A, B로 주어지는 데 이는 A가 B 앞에 서야한다는 뜻이다.

  • 문제 분류
    • Graph, Topological Sorting


2. 알고리즘 설계

  • 위상정렬(Topological Sorting) 기본 문제였다.
    • 개념은 여기에 정리해 두었다.
  • 주어지는 M개의 입력 중 각각을 A, B라고 했을 때 그래프는 A->B의 형태가 될 것이다.
  • B가 가르켜진 횟수를 저장해둔다.
  • 한번도 가르켜지지 않은 노드 번호가 있다면, 큐에 넣어준다.
    • 참고로 반드시 한 개 이상 있다.
  • 큐가 빌 때까지 반복
    • 현재 큐의 가장 앞 원소를 꺼낸다.
      • 이건 먼저 선택되어야 하는 노드이다.
      • 출력한다 or result에 저장
    • 가장 앞 원소가 가르키고 있는 원소의 가르킴 횟수를 하나씩 깎는다.
      • 만약 깎았는데 횟수가 0이 되면 큐에 넣는다.


3. 전체 코드

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

const int SZ = 32'002;
int n, m, from, to, deg[SZ];
vector<int> res;
vector<int> adj[SZ];
queue<int> q;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    while(m--) {
        cin >> from >> to;
        adj[from].push_back(to);
        deg[to]++;
    }

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

    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        res.push_back(cur);

        for(int nxt : adj[cur]) {
            deg[nxt]--;
            if(deg[nxt] == 0) q.push(nxt);
        }
    }

    for(int a : res)
        cout << a << ' ';

    return 0;
}