[Algorithm]Baekjoon 1766번 : 문제집

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

1766번: 문제집

 
using namespace std;
 
int n, m, a, b;
vector<vector<int>> graph(32001);
priority_queue<int, vector<int>, greater<int>> pq;
int inDegrees[32001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
        graph[a].push_back(b);
        ++inDegrees[b];
    }
 
    for (int i = 1; i <= n; ++i)
    {
        if (inDegrees[i] == 0)
        {
            pq.push(i);
        }
    }
 
    vector<int> answer;
 
    while (!pq.empty())
    {
        int curNum = pq.top();
        pq.pop();
        answer.push_back(curNum);
 
        for (int i = 0; i < graph[curNum].size(); ++i)
        {
            int child = graph[curNum][i];
            --inDegrees[child];
 
            if (inDegrees[child] == 0)
            {
                pq.push(child);
            }
        }
    }
 
    for (int temp : answer)
    {
        cout << temp << ' ';
    }
}
 
 
 
 

 

그냥 위상정렬 기본문제에서 아주 살짝만 바꾼 문제이다.

처음에 문제설명만 보고 다중상속이 아닌 리니어한 상속관곈줄 알고 코드를 작성했는데, 실패하고나서 보니 다중상속관계였다.

사실 리니어한 관계였으면 골드2일리가 없긴했다..

 

기본적으로 순서에 맞게 문제푸는순서를 출력하면 되는데, 대신 이문제에서는 선택할 수 있는 문제가 여러개일 때, 가장 낮은번호의 문제를 선택해야하기 때문에 그것만 코드로 작성해주면 된다. 나는 우선순위큐에 담아서 편하게 풀었다.