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

문제

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

---

문제 요약

1번부터 N번 문제까지 존재하는 문제집을 풀려고 한다.

 

규칙에 따라 문제를 풀 순서를 정해야 한다.

 

1. N개의 문제를 모두 풀어야 한다.

2. 먼저 푸는 것이 좋은 문제를 반드시 먼저 푼다.

3. 가능하면, 쉬운 문제부터 풀어야 한다.

 

문제의 개수와 먼저 푸는 것이 좋은 문제 정보가 주어졌을 때, 순서를 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n, m;

vector<int> edges[32001];
priority_queue<int> pq;

int in_degree[32001];

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        in_degree[b]++;
    }

    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == 0) {
            pq.push(-i);
        }
    }

    while (!pq.empty()) {
        int x = pq.top();
        x = -x;
        pq.pop();

        for (int i = 0; i < edges[x].size(); i++) {
            int y = edges[x][i];

            in_degree[y]--;

            if (in_degree[y] == 0) {
                pq.push(-y);
            }
        }

        cout << x << " ";
    }

    return 0;
}

---

코드 설명

위상 정렬을 이용한다.

 

각 문제를 노드로, 먼저 푸는 것이 좋은 노드의 정보를 간선으로 표시한다.

 

1. 유향 그래프 정보를 Vector에 저장한다.

 

2. 해당 노드보다 먼저 푸는 것이 좋은 노드 개수인 in_degree 배열을 정의한다.

 

3. 우선 순위 큐에 in_degree가 0인 노드들을 먼저 삽입한다.

(쉬운 문제부터 풀어야 하므로 -를 붙여서 push하고, 다시 -를 붙여서 pop한다.)

 

4. 우선 순위 큐에서 노드를 하나씩 빼서 해당 노드가 가리키는 간선을 삭제한다.

(가리키는 노드의 in_degree를 1 감소시킨다.)

 

5. 간선을 삭제했을 때, in_degree가 0이 되는 노드는 우선 순위 큐에 삽입한다.