백준 1766 문제집 - 우선순위 큐를 활용한 위상정렬 문제 (c++)

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

1766번: 문제집

이 문제는 위상정렬을 이용하되, 조건이 하나 붙게 된다.

바로 쉬운 문제 순서대로 풀어야 한다는것.

이를 활용하기 위해서는, 항상 큐에 들어있는 문제 중 쉬운 문제 순으로 풀도록 우선순위 큐를 활용해서 풀어야 한다.

 

우선순위 큐는 priority_queue 라는 stl로 존재한다.

나머지 알고리즘은 백준 2252번과 완전히 동일하다.

2252번을 풀었으면 이 1766번 문제도 쉽게 풀 수 있을것이다..

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAX = 32001;
int N,M;
vector<int> graph[MAX];
int numOfPredecessor[MAX];
 
void bfs(){
    priority_queue<int,vector<int>,greater<int>> q;
    for(int i=1; i<=N; i++){
        if(numOfPredecessor[i]==0)
            q.push(i);
    }
    while(!q.empty()){
        int cur = q.top();
        q.pop();
        cout<<cur<<" ";
        for(int i=0; i<graph[cur].size(); i++){
            numOfPredecessor[graph[cur][i]]--;
            if(numOfPredecessor[graph[cur][i]]==0)
                q.push(graph[cur][i]);
        }
    }
}
 
int main(void){
    cin>>N>>M;
    int a,b;
    for(int i=0; i<M; i++){
        cin>>a>>b;
        graph[a].push_back(b);
        numOfPredecessor[b]++;
    }
    bfs();
}