[BOJ] 문제집(1776)

[백준(BOJ)] 문제집(1776) C++

문제 : BOJ_1776번 문제집

문제 설명

위상정렬, bfs, 우선순위 큐

1~N 번까지 문제가 주어질 때, 세 가지 조건이 주어집니다.

(1) N 개의 문제는 모두 풀어야 되고
(2) 문제에 대한 정보(M)에 맞게 순서대로 풀어야 되고,
(3) 가능하면 낮은 수의 쉬운 문제부터 풀어야 됩니다. 이 문제는 위상 정렬을 이용하여 주어진 문제들끼리의 위상을 파악해야 되는 것도 물론이지만,
이 문제는 3번 문제가 추가되면서 그냥 위상 정렬로만은 풀 수 없는 문제가 되어버립니다.
서로 방향성이 있는 문제는 그 순서에 맞게 풀어야 되지만,
서로 간의 방향이 없는 문제들끼리는 낮은 수의 문제부터 푸는 게 이 문제의 포인트입니다.

---

Solution

이 문제는 우선 bfs와 indegree[] 배열을 이용한 위상 정렬을 해야 되는데, 이때 우선순위 큐를 이용해 오름차순으로 뽑아주는 게 풀이 방법입니다.
1,2,3,4의 문제가 있고, 4번을 2번보다 먼저 풀어야 된다고 생각해본다면, 2번은 4와의 하나의 indegree가 사라지기 전까지 우선순위 큐에 들어가지 않습니다.
indgree[i]가 1 이상인 수들은 indegree[i]가 0이 되기 전까지 큐에 들어가지 않으므로, indegree[i]==0인 수들이 우선순위 큐에 들어가고 나온 뒤에 순서대로 큐에 들어가고 출력되게 됩니다.

---

Description

1. 우선순위 큐에서 greater로 오름차순 구현
2. 풀어야 하는 문제들은 pop과 동시에 cout으로 출력

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int n, m, line[32001];
priority_queue <int, vector<int>, greater<int>> pq; // 우선순위 큐
vector<int> adj[32001];
int main(void) {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        line[b]++;
    }
    for (int i = 1; i <= n; i++) {
        if (line[i] == 0) pq.push(i);
    }
    while (!pq.empty()) {
        int now = pq.top();
        cout << now << ' ';
        pq.pop(); // cout출력과 함께 pop
        for (int i = 0; i < adj[now].size(); i++) {
            int next = adj[now][i];
            line[next]--;
            if (line[next] == 0) pq.push(next); // indegree가 0일 때 push해줌으로써 두번 째 조건을 만족
        }
    }
    return 0;
}