백준 1766 문제집 | C++

 

 

이번 포스팅은 백준 1766번 문제집입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/1766

1766번: 문제집

 

 

 

기본 알고리즘

위상정렬 Topological Sort

우선순위 큐 Priority Queue

 

풀이

문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.

 

line 14  priority_queue<int, vector<int>, greater<int>> pq;

오름차순 정렬 우선순위 큐 사용

 

 

 

 

전체 코드

 

//백준1766 문제집                                                            
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main() {
    const int MAX = 32001;
    int N, M;
    cin >> N >> M;
 
    vector<int> adj[MAX];
    int inDeg[MAX] = { 0, };
    priority_queue<int, vector<int>, greater<int>> pq;
 
    while (M--) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        inDeg[b]++;
    }
 
    for (int i = 1; i <= N; i++) {
        if (inDeg[i] == 0) {
            pq.push(i);
        }
    }
 
    while (!pq.empty()) {
        int cur = pq.top();
        pq.pop();
        cout << cur << " ";
 
        for (int i = 0; i < adj[cur].size(); i++) {
            int next = adj[cur][i];
            inDeg[next]--;
 
            if (inDeg[next] == 0) {
                pq.push(next);
            }
        }
    }
 
    return 0;
}