BOJ - 1766 문제집

1766번 문제집

문제를 풀어야 하는데, 좀 더 쉽게 문제를 풀기 위해 먼저 풀면 좋은 문제들이 주어진다.

또한 문제 번호가 커질수록 난이도 역시 어려워 진다.

모든 문제들을 풀어야 하는데, 먼저 풀면 좋은 문제들이 있다면 그 문제들을 반드시 다 푼 후에 해당 문제를 풀어야 하고, 문제는 가능하면 쉬운 문제부터 풀어야 한다는 조건이 있다.

문제 풀이 전략

문제 풀이 순서를 지키면서 모든 문제를 풀어야 하기 때문에 이 문제는 위상정렬로 해결할 수 있다.

하지만 문제 별 난이도가 있다는 점을 고려하여 똑같은 순위의 문제가 있다면 쉬운 문제를 풀어야 하기 때문에 이 점은 우선순위 큐를 활용하여 해결할 수 있다.

우선 문제의 순서를 입력 받으면 그래프를 만들면서 부모 노드의 개수를 저장해 준다.

부모 노드가 없는 문제들이 가장 먼저 풀려야 하는 문제들이므로 우선순위 큐에 저장한다.

그리고 현재 탐색 대상의 되는 노드의 자식노드들 중 부모가 이제 없어지는 경우라면 우선순위 큐에 삽입하며 모든 노드에 대해 이 과정을 반복한다.

코드

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

using namespace std;
vector<int> v[32001];
int ind[32001];
int n,m;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    priority_queue<int> q;
    for(int i=1;i<=n;i++){
        if(ind[i] == 0)
            q.push(-i);
    }

    while(!q.empty()){
        int x = -q.top();
        q.pop();

        cout << x << " ";
        for(int i=0;i<v[x].size();i++){
            ind[v[x][i]]--;
            if(ind[v[x][i]] == 0)
                q.push(-v[x][i]);
        }
    }
    return 0;
}

출처 : https://www.acmicpc.net/problem/1766