[BOJ] 14567. 선수과목 (Prerequisite) (C++)

문제

과목의 수 N과 선수 조건의 수 M이 주어진다.

어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다.

1. 한 학기에 들을 수 있는 과목 수에 제한이 없다
2. 모든 과목은 매 학기 항상 개설된다

모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 출력

생각할 것

• 위상 정렬을 이용하자
• 연결된 과목에 1을 더해 과목 이수에 소요되는 값을 추가하자

코드

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M, A, B;
    cin >> N >> M;

    vector<vector<int>> adj(N + 1);
    vector<int> inDegree(N + 1);
    for (int i = 0; i < M; i++) {
        cin >> A >> B;
        adj[A].push_back(B);
        inDegree[B]++;
    }

    queue<int> q;
    vector<int> res(N + 1, 1);
    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    for (int i = 1; i <= N; i++) {
        if (q.empty()) continue;
        int cur = q.front();
        q.pop();

        for (int j = 0; j < adj[cur].size(); j++) {
            int next = adj[cur][j];
            if (--inDegree[next] == 0) {
                q.push(next);
                res[next] = res[cur] + 1;
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        cout << res[i] << " ";
    }

    return 0;
}