[백준] 2252번: 문제집 / C++

✏️ 문제 링크

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

1766번: 문제집

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

기본적으로 위상정렬 문제인데! + min heap이 합쳐진 문제이다.

먼저 풀어야 하는 문제를 풀고 queue에 넣을 때에 더 쉬운 문제들 부터 풀어야하니, queue안에서 가장 쉬운 문제들로 정렬이 되어야 하기 때문에 priority_queue를 사용해서 문제를 풀 수 있다!

 

 

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
#define MAX 32001
vector<int> entry(MAX, 0);
vector<int> vec[MAX];
int main(){
    
    int N, M; cin>>N>>M;
    while(M--){
        int a,b; cin>>a>>b;
        entry[b]++;
        vec[a].push_back(b);
    }
    
    priority_queue<int> pq; 
    for(int i=1; i<=N; i++){
        if(entry[i]==0) pq.push(-i);
    }
    while(!pq.empty()){
        int t=-pq.top(); pq.pop();
        cout<<t<<" ";
        for(int i=0; i<vec[t].size(); i++){
            int nxt=vec[t][i];
            entry[nxt]--;
            if(entry[nxt]==0)  pq.push(-nxt);
        }
    }
    
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐