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

백준의 문제집(1766) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저 푸는 것이 좋은 문제일 조건이 붙는 문제들이 주어질 때, 문제를 어떤 문제들부터 풀어야할지 순서를 출력해야 하는

문제이다.

본인은 "일의 순서를 정하는 것"이라는 점에서 위상정렬을 이용해서 구현해보았다.

일의 순서를 정할 때, 현재 일을 처리할 수 있는지를 고려해주어야 하는데 이 문제는 한 가지 더 고려해 주어야 한다.

바로 "쉬운문제부터 풀어야한다." 라는 것이다. 문제의 번호가 작을수록 더 쉬운문제이고, 현재 문제를 내가 지금 당장

풀 수 있는 문제라 하더라도, '현재 풀 수 있는 문제가 여러개일 경우, 더 쉬운 문제를 풀도록' 구현해 주어야 한다.

따라서, 본인은 우선순위큐를 이용해서 현재 풀 수 있는 문제들을 큐에 넣어주었다.

우선순위큐를 이용해서 더 쉬운 문제가 더 높은 우선순위를 갖도록 구현해 주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 32010
using namespace std;
 
int N, M;
int Entry[MAX];
vector<int> Problem[MAX];
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Problem[a].push_back(b);
        Entry[b]++;
    }
}
 
void Solution()
{
    priority_queue<int> Q;
 
    for (int i = 1; i <= N; i++)
    {
        if (Entry[i] == 0) Q.push(-i);
    }
 
    while (Q.empty() == 0)
    {
        int Cur = -Q.top();
        Q.pop();
 
        cout << Cur << " ";
 
        for (int i = 0; i < Problem[Cur].size(); i++)
        {
            int Next = Problem[Cur][i];
            Entry[Next]--;
            
            if (Entry[Next] == 0) Q.push(-Next);
        }
    }
    cout << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}