[ 백준 / C++ ] 1766 : 문제집

[ 문제 ]

 

1766번: 문제집 (acmicpc.net)

 

[ 접근방법 ]

 

입력을 받을 때 "먼저 푸는 것이 좋은 문제" 수를 체크해준다 ( 배열 d[index] ).

 

d[index] > 0 이면  "먼저 푸는 것이 좋은 문제" 가 존재한다는 의미이다.

즉, d[index] = 0 인 문제부터 풀어야 한다.

 

또한, 가능한 쉬운 ( index가 작은 ) 문제부터 풀어야 하는데, d[index] = 0 인 문제를

우선순위 큐에 넣고 이를 해결하였다.

 

한 번 푼 문제는 우선순위 큐에서 제거하며, 연결된 문제들의 d[index] 를 감소시키고,

d[index] = 0 이 되면 우선순위 큐에 넣어주고 이를 반복한다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m, a, b, d[32005];
vector<int> v[32005];
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    while (m--)
    {
        cin >> a >> b;
        v[a].push_back(b);
        d[b]++;
    }

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

    while (!pq.empty())
    {
        int pt = pq.top();
        pq.pop();
        cout << pt << " ";

        for (auto i : v[pt])
        {
            d[i]--;
            if (!d[i])
                pq.push(i);
        }
    }

    return 0;
}