백준 14567번: 선수과목 (Prerequisite) (C++), 위상 정렬

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

14567번: 선수과목 (Prerequisite)

이 문제는 Topological Sort가 필요한 알고리즘으로 이에 대해 알아보자.

(+공부했던 블로그 https://m.blog.naver.com/ndb796/221236874984)

 

어떤 일들에 대한 순서들이 주어졌을 때, 그 순서를 결정해주기 위한 알고리즘이다.

어떠한 일을 노드라고 하자.

각 노드마다 진입 차수가 존재한다.

 

진입 차수란 어떤 한 노드를 가리키는 노드의 개수(차수)가 몇 개인지를 나타낸다.

 

1. 진입 차수가 0인 노드들을 큐에다가 담고,
2. 큐에 담긴 노드들이 가리키는 노드들의 진입 차수를 하나씩 줄인다.
3. 이 과정에서 또 진입 차수가 0이 된 노드들을 큐에 담는 형식으로 진행된다.

다만, Topological Sort에서는 DAG(Directed Acyclic Graph)만 허용된다.

사이클이 존재할 경우, 다른 노드들을 위상 정렬에 포함시키지 않은 케이스가 발생할 수 있기 때문이다.

그리고, 이론적으로 사이클이 있을 경우에 꼬리 물기 형식으로 일의 순서가 돌아가면 안 된다.

 

시간 복잡도는 O(V + E)이다.

 

[AC 코드]

#include <iostream>
#include <vector>
#include <queue>
#define MAX (1000 + 1)
using namespace std;

int n, m;
int inDegree[MAX]; // 진입 차수
vector<int> graph[MAX];
int result[MAX];

void topologySort(){
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(inDegree[i] == 0) q.push(i);
        result[i] = 1;
    }
    
    while(!q.empty()){
        int x = q.front();
        q.pop();
        
        for(int i = 0; i < graph[x].size(); i++){
            int next = graph[x][i];
            inDegree[next]--;
            if(inDegree[next] == 0){
                q.push(next);
                result[next] = max(result[next], result[x] + 1);
            }
        }
    }
    
    /*
    for(int i = 1; i <= n; i++){
        if(q.empty()){
            cout << "Cycle Exist";
        }
        int x = q.front();
        q.pop();
        
        result[x] = i;
        for(int j = 0; j < graph[x].size(); j++){
            int y = graph[x][j];
            if(--inDegree[y] == 0){
                q.push(y);
            }
        }
    }
    */
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        inDegree[b]++;
    }
    
    topologySort();
    for(int i = 1; i <= n; i++){
        cout << result[i] << ' ';
    }
    return 0;
}