백준 1766 - 문제집

백준 1766 문제 바로가기

풀이

• A번 문제는 B번 문제보다 먼저 풀어야 한다. (A→B) indegree[B]의 값을 1씩 증가시킨다.
• indegree[num] 값이 0인 위치의 정점번호(num)를 큐에 넣는다.
• 이때 가능하면 쉬운 문제부터 풀어야 하므로, 큐에서 문제 번호가 작은 순서대로 꺼내어 확인한다. (priority queue) 꺼낸 값(now)은 출력한다.
• 현재 정점(now)이 향하고 있는 정점(next)을 알 수 있고, --indegree[next] 값이 0일 때 next를 큐에 넣으면서 반복한다.

소스 코드

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

int N;
int M;
vector<int> adj[32001];
int indegree[32001];

struct cmp {
    bool operator()(const int A, const int B) {
        return A > B;
    }
};

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> N >> M;
    for (int i = 0, A, B; i != M; ++i) {
        cin >> A >> B;
        adj[A].push_back(B);
        ++indegree[B];
    }


    priority_queue<int, vector<int>, cmp> pq;
    for (int num = 1; num <= N; ++num) {
        if (indegree[num] == 0) {
            pq.push(num);
        }
    }

    while (!pq.empty()) {
        int now = pq.top();
        pq.pop();
        cout << now << ' ';
        for (int next : adj[now]) {
            if (--indegree[next] == 0) {
                pq.push(next);
            }
        }
    }

    return 0;
}