(BOJ) 1766 풀이

#include<bits/stdc++.h>
using namespace std;
int N,M;
int in_degree[32001];
vector<int> v[32001];
priority_queue<int,vector<int>,greater<int>> pq;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> N >> M;
    for(int i=1;i<=M;i++){ // 입력받은뒤, 인접리스트에 넣고, 진입차수를 증가시킨다.
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        in_degree[b]++;
    } 
    // for(int i=1;i<=N;i++){ // test
    //     cout << in_degree[i] << '\n';
    // }
    for(int i=1;i<=N;i++){ // 진입차수가 0인 정점을 push
        if(in_degree[i]==0){
            pq.push(i);
        }
    }
    while(!pq.empty()){
        int x=pq.top();
        pq.pop();
        cout << x << ' '; 
        for(auto i:v[x]){ // 연결된 정점들을 끊으면서 0이 되는 것들을 push
            if(--in_degree[i]==0)
                pq.push(i);
        }
    }
}

문제를 푸는 순서를 정하는 문제이다.

위상정렬을 사용해서 풀 수 있다.

위상정렬을 간단히 설명하면, DAG (Direct Acyclic Graph) 에만 적용이 가능한데,

DAG 는 사이클이 발생하지 않는 그래프이다.

초등학생	중학생	고등학생	취업	창업	돈많이벌기
			대학생	대학교졸업

만약 돈많이벌기 → 초등학생으로 이어지면, 이는 사이클이 발생하는 것이고 위상정렬 적용이 불가능하다.

 

BFS 를 이용한 방식으로 위상정렬을 구현해보면,

초등학생부터 인접리스트의 진입정점을 하나씩 감소시키면서, 0이 되는 것이 있으면 큐에 넣고 다시 도는 식으로 BFS 가 진행된다.

이 때 고등학생에서 두 갈래로 나뉘는데, 위 문제에서는 이런 경우에 가능하면 쉬운 문제 (숫자가 작다) 부터 풀라고 했으니, 우선순위 큐를 사용했다.