[백준] 2252: 줄 세우기 (feat.위상정렬)

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

2252번: 줄 세우기

 

위상정렬(Topology Sort)는 순서(선후)가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 사용하는 알고리즘이다.

 

위상 정렬은 여러 개의 답이 존재할 수 있다.

또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다. 사이클이 발생하는 경우에는 위상 정렬을 수행할 수 없다.

위상 정렬은 시작점이 존재해야 하는데, 사이클에서는 시작점을 찾을 수 없기 때문이다.

 

Queue를 사용한 위상정렬 알고리즘

1. 진입차수가 0인 정점을 Queue에 삽입한다.
2. Queue에서 원소를 꺼내 연결된 모든 간선을 제거한다.(진입차수 감소)
3. 간선 제거 이후에 진입차수가 0이 된 정점을 Queue에 삽입한다.
4. Queue가 빌 때까지 2~3번을 반복한다. 모든 원소를 방문하기 전에 Queue가 빈다면 사이클이 존재하는 것이고, 모든 원소르 ㄹ방문했다면 Queue에서 꺼낸 순서가 위상 정렬의 결과이다.

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
vector<vector<int>> students(32001);
vector<int> indegree(32001, 0);
queue<int> q;
vector<int> result;
int main(void) {
    int n, m, a, b;
    cin >> n >> m;
    for(int i =0;i < m;i++) {
        cin >> a >> b;
        indegree[b]++;
        students[a].push_back(b);
    }

    for(int i = 1;i <= n;i++) {
        if (!indegree[i]) q.push(i);
    }

    for(int i = 1;i <= n;i++){
        if(q.empty()) {
            // 사이클 발생
            return 0;
        }
        int num = q.front();
        q.pop();
        result.push_back(num);
        for(auto j : students[num]) {
            if(--indegree[j] == 0) {
                q.push(j);
            }
        }
    }

    for(auto r: result) {
        cout << r << " ";
    }
}

 

참고

https://m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)