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

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

1766번: 문제집

풀이

위상 정렬이라는 개념도 제대로 모르고있었던 위상정렬 문제이다...
그래서 공부하며 포스팅하고 문제를 다시 풀어보았다.

입력란에 첫줄은 문제의 갯수와 조건의 갯수를 나타내고,
두번째줄 세번째줄을 보면 먼저 풀어야하는 문제 조건을 나타낸다.
=> (4 - 2), (3 - 1)

degree 배열에 해당 번호에 들어오는 선의 수를 저장하고
2차원 벡터에 간선의 방향을 정해준다. (4 -> 2, 3 -> 1)

난이도 순으로 풀어야 하기에 우선순위 큐를 오름차순으로 정렬 후, 해당 원소에 들어오지 않는 번호들을 push 해준다.
이후 큐에 들어있는 top을 차례대로 출력해주고, pop 하면서 해당 큐의 top이 가리키는 번호가 있으면 다시 큐에 push 해준다.

Code ( C++ )

#include <iostream>
#include<queue>
#include<vector>
using namespace std;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int degree[32000] = { 0 };
    vector<int> vt[32000];
    priority_queue<int, vector<int>, greater<int>> pq;
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        degree[b]++;
        vt[a].push_back(b);
    }

    for (int i = 1; i <= n; i++) {

        if (degree[i] == 0) {
            pq.push(i);
        }

    }
    while (!pq.empty()) 
    {
        int qNum = pq.top();
        pq.pop();
        cout << qNum << ' ';

        for (int i = 0; i < vt[qNum].size(); i++) {

            int next = vt[qNum][i];

            if (--degree[next] == 0) {
                pq.push(next);
            }
        }
    }
}