백준 14567 - 선수과목, C++, 위상정렬

14567번: 선수과목 (Prerequisite)

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

int n, m, a, b;
int enterance[1001];
int howmany[1001];
vector<int> edge[1001];

void Topology(){
    int cur_sem = 1;
    queue<pair<int, int>> q;

    for(int i = 0; i < n; i++){
        if(enterance[i] == 0){
            q.push(make_pair(i, 1));
        }
    }

    while (!q.empty()){
        int cur = q.front().first;
        int cur_season = q.front().second;
        q.pop();

        howmany[cur] = cur_season;

        for(int i = 0; i < edge[cur].size(); i++){
            int nextCur = edge[cur][i];
            enterance[nextCur]--;

            if(enterance[nextCur] == 0){
                q.push(make_pair(nextCur, cur_season+1));
            }
        }
    }
    
}


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

    // input
    cin >> n >> m;
    
    for(int i = 0; i <= n; i++)
        howmany[i] = 1;

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

    // topology sory
    Topology();

    // print
    for(int i = 1; i <= n; i++){
        cout << howmany[i] << " ";
    }
    cout << '\n';
    return 0;
}

---

 위상성렬을 사용하면 되는 문제로 큐에 '현재 학기'를 같이 저장해서 사용하면 됩니다. 매번 학기를 저장하는 비효율이 있기는 하지만 문제의 케이스가 얼마 되지않고 시간제한, 메모리도 넉넉해 위 방법을 사용했습니다.

 

 선이수 과목을 진입점으로 보고 풀이한 것으로 위상정렬의 특징인 '순서가 여러개 나온다'는 특징에 구애받지 않으므로 위상정렬을 간단하게 쓸 수 있습니다.