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

문제

1766번: 문제집

풀이

방향 비순환 그래프, 위상 정렬, 우선순위 큐

 

방향 비순환 그래프, 위상 정렬, 우선순위 큐를 합친 문제이다. 기본적인 풀이 방법은 다음과 같다. 

• B문제를 풀기 위해서는 A문제를 먼저 풀어야 한다. 
• 입력으로 A, B가 들어오면 A의 outdegree로 B가 추가되고, B의 indegree가 1 증가한다. 
• 문제는 쉬운 문제부터 풀어야 하므로, 우선순위 큐로 현재 풀 수 있는 문제 중에서 난이도가 가장 낮은 문제가 top에 위치할 수 있도록 한다. 

 

• indegree가 0인 문제가 우선순위 큐에 들어간다. top에 있는 문제를 풀면 해당 문제의 outdegree에 해당하는 문제들의 indegree가 1 줄어든다. 
• indegree가 0이 된 문제는 풀 수 있으므로, 우선순위 큐에 넣는다. 
• 위를 반복

코드

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

using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
vector<int> indegree;
vector<vector<int>> outdegree;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;

    indegree.resize(N + 1, 0);
    outdegree.resize(N + 1);

    for (int i = 0; i < M; ++i)
    {
        int A, B;
        cin >> A >> B;

        // B를 풀기위해서는 A를 먼저 풀어야 한다.
        indegree[B]++;
        outdegree[A].push_back(B);
    }

    for (int i = 1; i <= N; ++i)
    {
        // 현재 먼저 풀어야할 문제가 없는 문제부터 pq에 들어간다.
        if (indegree[i] == 0)
        {
            pq.push(i);
        }
    }

    while (!pq.empty())
    {
        int current = pq.top();
        pq.pop();

        cout << current << " ";

        // 현재 푼 문제의 outdegree에 해당하는 문제들의 indegree가 1 줄어든다.
        for (int i = 0; i < outdegree[current].size(); ++i)
        {
            int next = outdegree[current][i];
            indegree[next]--;

            // outdegree가 0이 되었다면 이제 풀 수 있으므로, pq에 넣는다.
            if (indegree[next] == 0)
            {
                pq.push(next);
            }
        }
    }

    return 0;
}