[C++] 백준 14567: 선수과목(Prerequisite)

문제 이해

- 모든 전공 과목을 들어야 졸업할 수 있다.

- 특정 과목은 선수과목을 모두 들어야만 들을 수 있다.

- 한 학기에 들을 수 있는 과목 수에 제한은 없다.

- 모든 과목은 매 학기 개설된다.

 

- N: 과목의 수 (1 ~ 1,000, 10^3)

- M: 선수 조건의 수(0 ~ 500,000, 10^5)

- 시간 제한: 5초

- 메모리 제한: 256MB

 

<출력>

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

 

 

문제 풀이

각 과목에 대해 선수 과목이 있다는 지문은 선행 관계가 주어진 그래프라고 볼 수 있다.

=> 위상 정렬을 사용해서 풀자!

 

 

 

이 문제의 특별한 점은 각 과목마다 이수하는 데 걸리는 학기의 수를 구해야 한다는 점이다.

걸리는 학기의 수를 배열을 하나 설정해 DP를 써주면 쉽게 풀 수 있을 거 같았다.

 

DP를 쓰는 다른 위상정렬 문제처럼

순서쌍을 통해 이미 최소 관계가 주어졌으므로 dp배열의 값을 구할 때는 max를 사용해야 한다는 점을 주의하자.

 

선수 과목 중에서,

나중에 수강하는 과목을 듣고 나서 다음 수업을 들을 수 있으므로

max를 사용하자.

dp[next] = max(dp[next], dp[now]+1);

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

vector <int> v[1005];
int inDegree[1005];
int dp[1005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin>>n>>m;

    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        v[a].push_back(b);
        inDegree[b]++;
    }

    queue <int> q;
    for(int i = 1; i <= n; i++){
        if(inDegree[i] == 0){
            q.push(i);
        }
        dp[i] = 1;
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();

        int size = v[now].size();
        for(int i = 0; i < size; i++){
            int next = v[now][i];
            inDegree[next]--;
            if(inDegree[next] == 0){
                q.push(next);
                dp[next] = max(dp[next], dp[now]+1);
            }
        }
    }

    for(int i = 1; i <= n; i++){
        cout<<dp[i]<<" ";
    }
    return 0;
}