[백준] 1766 문제집 (C++)

문제

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

1766번: 문제집

 

 

풀이

한 문제, 한 문제씩 풀어나가는 것을 그래프에 대입하여 노드를 탐색하는 과정으로 생각해봅시다.

 

조건에 의해 모든 노드를 탐색해야 하고, 
먼저 푸는것이 좋은 문제를 반드시 먼저 풀어야 하므로 선행 노드를 반드시 탐색해야 합니다.
따라서 위상정렬로 문제를 해결해야 합니다.

그런데 쉬운 문제(번호가 낮은 노드)부터 해결해야 하므로 현재 풀 수 있는 문제(indegree == 0) 중에서 가장 번호가 작은 문제를 선택해야 합니다.
한 문제를 풀고 다음에 풀 문제를 선택하기 위해 1번부터 N번까지 탐색할 필요 없이,
우선 순위 큐를 이용하면 현재 풀 수 있는 문제들 중 가장 쉬운 문제를 찾을 수 있습니다.

 

우선 순위 큐에 현재 풀 수 있는 모든 문제를 넣고 하나씩 출력하며 탐색해 나가면 됩니다.

 

 

코드

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

using namespace std;

int n, m;
vector<vector<int>> edges;
vector<int> indegree;

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

    cin >> n >> m;
    edges.resize(n+1, vector<int>());
    indegree.resize(n+1, 0);
    for (int i=0; i<m; ++i)
    {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        ++indegree[b];
    }

    priority_queue<int, vector<int>, greater<int>> q;
    for (int i=1; i<n+1; ++i)
    {
        if (indegree[i] == 0)
        {
            q.push(i);
        }
    }

    while (!q.empty())
    {
        int cur = q.top();
        q.pop();

        cout << cur << " ";

        for (int next : edges[cur])
        {
            --indegree[next];

            if (indegree[next] != 0)
                continue;

            q.push(next);
        }

    }
    cout << "\n";
    return 0;
}