[백준/C++] 1766번: 문제

문제 & 링크

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

풀이

1. 선행 문제가 존재하는 문제의 경우 선행 문제 다음으로 풀이되어야 하기에, 위상 정렬 문제이다.

2. 가장 쉬운 문제, 즉 문제 번호가 낮은 문제가 우선적으로 풀려야 한다.

3. 입력을 받을 때 인접 리스트의 형태로 문제 간의 관계를 저장한다. 또한 선행 문제가 존재하는 문제의 경우 degree를 1씩 늘리며 선행 문제의 개수를 저장한다.

4. 선행 문제가 존재하지 않는 문제(degree가 0인 문제)를 min-heap에 넣는다.

5. min-heap을 탐색하며 top을 출력 & pop하고, top을 선행 문제로 하는 다른 문제들의 degree를 1씩 낮춘다.

6. 1이 낮아진 degree가 0이라면, 선행 문제가 없다는 뜻으로 min-heap에 넣는다.

7. 5 - 6의 과정을 모든 문제가 출력될 때 까지 반복한다.

코드

#include <iostream>
#include <queue>

using namespace std;

int degree[32001];
vector<int> V[32001];

int main() {
    int N, M;
    cin >> N >> M;

    int A, B;
    priority_queue<int, vector<int>, greater<int>> pq;

    for (int i = 0; i < M; i++) {
        cin >> A >> B;

        V[A].push_back(B);
        degree[B]++;
    }

    for (int i = 1; i <= N; i++) {
        if (degree[i] == 0) pq.push(i);
    }

    while (!pq.empty()) {
        int tmp = pq.top();
        pq.pop();
        if (degree[tmp] == 0) {
            cout << tmp << " ";
            for (int i = 0; i < V[tmp].size(); i++) {
                degree[V[tmp][i]]--;
                if (degree[V[tmp][i]] == 0) pq.push(V[tmp][i]);
            }
        }
    }
}