[BOJ 백준] 1766번 문제집

문제

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

1766번: 문제집

접근

순서가 정해져 있는 작업을 차례대로 수행해야 할 때 위상 정렬(Topological Sort)을 사용한다. 따라서 이 문제는 위상 정렬을 이용해 문제를 풀었다.

위상 정렬(Topological Sort) 알고리즘에 관해 HeeJeong Kwon 님과 안경잡이개발자 님의 블로그를 참고했다.

이 문제에는 한 가지 조건이 더 있는데, 가능한 쉬운 문제부터 풀어야 한다는 조건이다. 여기서 쉬운 문제란 문제의 번호가 작은 순서이므로 우선순위 큐를 이용해 쉬운 문제부터 풀도록 해주었다.

 

코드

// BOJ_1766_문제집

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

using namespace std;

priority_queue<int> pq;
vector<int> graph[32001];
int sum[32001];

int main() {
    int n, m, u, v;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        sum[v]++;
    }
    for (int i = 1; i <= n; i++) {
        if (sum[i] == 0)
            pq.push(-i);
    }
    while (!pq.empty()) {
        int pl = pq.top();
        pq.pop();
        cout << -pl << ' ';
        for (int j = 0; j < graph[-pl].size(); j++) {
            int num = graph[-pl][j];
            sum[num]--;
            if (sum[num] == 0)
                pq.push(-num);
        }
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study