백준 1766번: 문제집 (C++)

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

1766번: 문제집

문제를 읽어보면 간단한 위상 정렬 문제인 것 같지만, 문제에서 주어진 3번 조건 "가능하면 쉬운 것부터 풀어야 한다."가 발목을 잡게 된다.

>> 위상 정렬을 하되, 오름차순으로 우선순위 큐에 집어놓고 위상 정렬을 돌리면 해결 가능하다.

 

[AC 코드]

#include <iostream>
#include <vector>
#include <queue>
#define MAX 32001
using namespace std;

int n, m;
int inDegree[MAX];
vector<int> adj[MAX];
vector<int> result;

struct cmp{
    bool operator()(int a, int b){
        return a > b;
    }
};

void topologicalSort(){
    priority_queue<int, vector<int>, cmp> pq;
    for(int i = 1; i <= n; i++){
        if(inDegree[i] == 0){
            pq.push(i);
        }
    }
    
    while(!pq.empty()){
        int now = pq.top();
        
        pq.pop();
        result.push_back(now);
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i];
            
            if(--inDegree[next] == 0){
                pq.push(next);
            }
        }
    }
}

int main(){
    cin >> n >> m;
    
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        inDegree[b]++;
        adj[a].push_back(b);
    }
    
    topologicalSort();
    
    for(int i = 0; i < result.size(); i++){
        cout << result[i] << ' ';
    }
    
    return 0;
}