[BOJ] 1766 문제집

1. 문제링크

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

2. 문제해설

이 문제는 위상정렬 문제에 priority_queue를 사용하는 문제이다.

1. 위상정렬을 한다.

2. 하는 중에 queue를 priority_queue로 바꿔서 위상정렬을 한다.

3. 소스코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define fio ios_base::sync_with_stdio(0); cin.tie(0);
#define MAX_NUM 32000
int main(){
    fio
    int n, m;
    int idgr[MAX_NUM+1]={0};
    vector<int> v[MAX_NUM+1];
    priority_queue<int, vector<int>, greater<int>> q;
    cin >> n >> m;
    for (int i=0; i<m; i++) {
        int s, e; cin >> s >> e;
        v[s].push_back(e);
        idgr[e]++;
    }
    
    for (int i=1; i<=n; i++) {
        if (idgr[i] == 0) {
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int cur = q.top(); q.pop();
        cout << cur << ' ';
        for(int next : v[cur]){
            if(--idgr[next] == 0){
                q.push(next);
            }
        }
    }
    
    cout << '\n';
    
    return 0;
}

4. 추가언급

왜 이 문제는 priority_queue를 써야하냐면 번호가 작은 문제일수록 쉬운 문제라고 하였으니 queue에 넣은 값중에서 가장 작은 값을 매번 뽑아서 문제를 푼다면 무조건적으로 풀어야하는 문제중에서는 가장 쉬운 문제를 풀게된다.