[백준] 14567번 선수과목 (Prerequisite) C++ 코드

코드

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

using namespace std;

int n,m,indegree[1003],x,y, visited[1003];
vector<int> adj[1003];

int main() {
  cin >> n >> m;
  for(int i = 0; i < m; i++) {
    cin >> x >> y;
    adj[x].push_back(y);
    indegree[y]++;
  }
  queue<int> q;
  for(int i = 1; i < n + 1; i++) {
    if(indegree[i] == 0) {
      q.push(i);
      visited[i] = 1;
    }
  }
  // 위상정렬
  while(q.size()) {
    int pn = q.front();
    q.pop();
    for(int i : adj[pn]) {
      indegree[i]--;
      if(indegree[i] == 0) {
        visited[i] = visited[pn] + 1;
        q.push(i);
      }
    }
  }

  for(int i = 1; i < n + 1; i++) {
    cout << visited[i];
    if(i != n) cout << " ";
  }
  cout << '\n';

  return 0;
}

풀이

선수과목 문제는 전형적인 위상정렬 문제이다. 몇 번째에 듣는지가 중요했는데, visited 배열을 이용해서 방문 순서를 체크해주면 된다.왜 저번엔 이게 그렇게 기억이 안났지... 오늘은 그냥 한 번에 생각났는데. 알기 힘들다 진짜.