[Algorithm] 1766: 문제집

• toc {:toc}

📦1766: 문제집

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-18
문제 확인하기

풀이

• 1, 2, 3번의 조건을 모두 만족하도록 만든다.
• 가능한 쉬운 문제부터 풀어야 하고 작은 수가 더 쉬운 문제이기 때문에 우선순위 큐를 이용하여 작은 순서부터 순차적으로 출력되도록 한다.
• 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀기 위해 나중에 풀어야 할 문제에 +1을 더해주고 먼저 풀어야 할 문제가 풀린 경우 -1을 하여 우선순위 큐에 넣어줌으로써 순서를 지킨다.

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;
 
int N, M, A, B;
int degree[32001];
vector<int> connect[32001];
 
void Input(){
    cin >> N >> M;
    for(int i=0; i<M; i++){
        cin >> A >> B;
        connect[A].push_back(B);
        degree[B]++;
    }
}
 
void Solution(){
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(int i=1; i<=N; i++){
        if(degree[i]==0){
            pq.push(i);
        }
    }
 
    for(int i=1; i<=N; i++){
        int cur = pq.top(); pq.pop();
 
        cout << cur << ' ';
 
        for(auto nxt : connect[cur]){
            degree[nxt]--;
            if(degree[nxt]==0){
                pq.push(nxt);
            }
        }
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
 
    return 0;
}