[C++] 백준 1766: 문제집

문제 이해

- N: 문제의 개수 (1 ~ 32,000, 10^4)

- M: 정보의 개수 (1 ~ 100,000, 10^5)

 

- 문제는 난이도 순서로 출제

- N개의 문제는 모두 풀어야 한다

- 먼저 풀으면 좋은 문제는 먼저 풀어야 한다

- 가능하면 쉬운 문제부터 풀어야 한다

 

 

문제 풀이

먼저 풀면 좋은 문제가 주어진다는 것은

특정 순서가 주어진 그래프의 전체 순서를 결정한다는 것과 같다.

 

즉, 위상 정렬을 사용해주면 쉽게 풀 수 있다.

 

 

다만, 이 문제에서 주의할 점은

'가능하면 쉬운 문제부터 풀어야 한다'는 점이다.

 

보통의 위상 정렬은 여러 개의 경우의 수가 가능하지만

위의 문구로 인해 이 문제는 한 가지 경우의 수만 나올 것이다.

 

가능하면 쉬운 문제를 풀기 위해

각 정점으로 들어가는 간선의 개수를 체크할 때 1개의 정점만 큐에 넣고,

큐에서 하나를 빼고난 뒤에 각 정점을 매번 체크해주어 1개씩 큐에 넣어주어야 한다.

 

 

큐에 넣어준 정점의 경우 다시 큐에 넣지 않기 위해 매우 큰 값으로 초기화해준다.

 

 

전체 코드

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

int n, m;
vector<int> v[32005];
int inDegree[32005];
queue<int> q;

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

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

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

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

        int size = v[now].size();
        for(int i = 0; i < size; i++){
            int next = v[now][i];
            inDegree[next]--;
        }

        for(int i = 1; i <= n; i++){
            if(inDegree[i] == 0){
                inDegree[i] = 100005;
                q.push(i);
                break;
            }
        }
    }
    
    return 0;
}