백준 14567 선수과목 (Prerequisite) | C++

 

 

이번 포스팅은 백준 14567번 선수과목 (Prerequisite)입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

 

 

 

기본 알고리즘

위상 정렬 (Topological Sort)

 

풀이

위상 정렬하면서 출력 배열(과목 번호가 인덱스)에 수강 학기 수를 저장한다.

 

1학기 부터 시작하므로 result 배열을 1로 초기화 한다.

 

q            1 4 6

result[i]    1 1 1

 

cur = 1

                 q            1 4 6 2 3

                 result[i]    1 1 1

next = 2

result[2] < result[1]+1 이므로 result[2] = 2

                 q            1 4 6 2 3

                 result[i]    1 1 1 2

next = 3

result[3] < result[1]+1 이므로 result[3] = 2

                 q            1 4 6 2 3

                 result[i]    1 1 1 2 2

 

cur = 4

                 q            1 4 6 2 3 5

                 result[i]    1 1 1 2 2 

next = 5

result[5] < result[4]+1 이므로 result[5] = 2

                 q            1 4 6 2 3 5

                 result[i]    1 1 1 2 2 2

 

cur = 6

                 q            1 4 6 2 3 5

                 result[i]    1 1 1 2 2 2

 

cur = 2

                 q            1 4 6 2 3 5

                 result[i]    1 1 1 2 2 2

next = 5

result[5] < result[2]+1 이므로 result[5] = 3

                 q            1 4 6 2 3 5

                 result[i]    1 1 1 2 2 3

 

cur = 3

                 q            1 4 6 2 3 5

                 result[i]    1 1 1 2 2 3

 

cur = 5

                 q            1 4 6 2 3 5

                 result[i]    1 1 1 2 2 3

 

 

 

 

전체 코드

#include <iostream>                                                            
#include <vector>
#include <queue>
using namespace std;
 
const int MAX = 1001;
vector<int> adj[MAX];
int inDeg[MAX];
queue<int> q;
int result[MAX];
 
int main() {
    int N, M;
    cin >> N >> M;
 
    int a, b;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        inDeg[b]++;
    }
 
    for (int i = 1; i <= N; i++) {
        if (inDeg[i] == 0) {
            q.push(i);
        }
        result[i] = 1; //1학기부터 시작(초기화)
    }
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 0; i < adj[cur].size(); i++) {
            int next = adj[cur][i];
            inDeg[next]--;
            if (inDeg[next] == 0) {
                q.push(next);
                result[next] = max(result[next], result[cur] + 1); //★
            }
        }
    }
 
    for (int i = 1; i <=N; i++) {
        cout << result[i] << " ";
    }
 
    return 0;
}