[백준] 1766 문제집 - 위상정렬, 우선순위 큐

[ 문제링크 ]

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

 

🚩 조건

1. 가능하면 쉬운 문제부터 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.

 

 

🚩 접근

1 -> 우선순위 큐 (최소 힙으로 쓰려면 아래처럼 선언)

priority_queue<int, vector<int>, greater<int>> qu;

2 -> 위상정렬

 

 

💻 코드 (C++)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int indegree[32001];
priority_queue<int, vector<int>, greater<int>> qu;
vector<int> adj[32001];
vector<int> ans;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int N, M, A, B;

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> A >> B;
        indegree[B]++;
        adj[A].push_back(B);
    }

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

	while (!qu.empty()) {
 		int size = adj[qu.top()].size();
		int top = qu.top();
		ans.push_back(qu.top());
		if (!qu.empty())qu.pop();
        if (size != 0) {
            for (int j = 0; j < size; j++) {
                indegree[adj[top][j]]--;
                if (indegree[adj[top][j]] == 0) {
                	qu.push(adj[top][j]);
                    }
                }
            }
        }

    for (int i = 0; i < ans.size(); i++) {
    	cout << ans[i] << " ";
    }
}