[ 백준 1766 ] 문제집 (c/c++)

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

 

 

[ 문제 요약 ]

문제가 난이도 순서로 출제되어 있는 문제집에서 문제를 난이도 순서대로 푼다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 할 때, 문제 푸는 순서를 출력한다.

 

 

[ 문제 풀이 ]

1. 먼저 푸는 것이 좋은 문제가 있는 문제의 경우 위상정렬을 이용해서 문제의 순서를 정해준다.

2. 이때 그냥 큐를 사용해서 위상정렬을 할 경우에는 문제의 난이도 순서를 고려하지 못한다.

3. 우선순위 큐를 이용해서 먼저 푸는 것을 풀 되 순서가 없는 경우 난이도가 쉬운 것부터 가져온다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, M;
int IN[32323];
vector<int> v[32323];
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
    cin >> N >> M;
    for (int i=0; i<M; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        IN[b]++;
    }

    for (int i=1; i<=N; i++) if(!IN[i]) pq.push(i);

    while (!pq.empty()){
        int cur = pq.top(); pq.pop();
        cout << cur << " ";
        for (auto i : v[cur]) if (!--IN[i]) pq.push(i);
    }
    
    return 0;
}

 

 

[ 주의할 점 ]

문제의 난이도 순서대로 주어지기 때문에 우선 순위 큐와 위상정렬을 이용해서 쉽게 구할 수 있었다.