Topological Sorting

순서가 있는 작업을 차례대로 수행할 때 순서를 결정해주기 위한 알고리즘으로, DAG(Directed Acyclic Graph)에만 적용 가능

구현

1. node간 순서와 진입차수를 아래와 같이 저장한다.

int indegree[32001]{};
vector<int> edge[32001];

for(int i=0; i<m; i++){
	int a, b; cin>>a>>b;
    edge[a].push_back(b); // a > b (a가 b보다 선행) 
    indegree[b]++; // a->b (b의 진입차수 ++)
}

2. 진입 차수가 0인 node(가장 먼저 수행하는 작업?!)를 찾아 queue에 넣어준다.

for(int i=1; i<=n; i++){
	queue<int> q, ans;
	if(indegree[i]==0){
    	q.push(i);
        ans.push(i);
	}
}

3. queue가 빌 때까지 다음의 과정을 반복한다.
   ① 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   ② 새롭게 진입차수가 0이 된 노드를 큐에 삽입 (진입 차수가 0 이 된 것 = 선행작업이 끝난 것)

while (!q.empty()){
	int x = q.front(); q.pop();
    for(int i=0; i<edge[x].size(); i++){
    	indegree[edge[x][i]]--;
        if(indegree[edge[x][i]]==0){
        	q.push(edge[x][i]);
            ans.push(edge[x][i]);
        }
    }
}

최종코드

Topological Sorting(위상정렬)을 이용한 백준 2252번: 줄 세우기 문제 풀이이다!

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

int n, m, indegree[32001]{};
vector<int> edge[32001];

void topologySort(){
    queue<int> q, ans;
    for(int i=1; i<=n; i++){
        if(indegree[i]==0){
            q.push(i);
            ans.push(i);
        }
    }
    while (1){
        if(q.empty()) break;
        int x = q.front(); q.pop();
        for(int i=0; i<edge[x].size(); i++){
            indegree[edge[x][i]]--;
            if(indegree[edge[x][i]]==0){
                q.push(edge[x][i]);
                ans.push(edge[x][i]);
            }
        }
    }
    for(int i=1; i<=n; i++) {
        cout << ans.front() << ' '; ans.pop();
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int a, b; cin>>a>>b;
        edge[a].push_back(b);
        indegree[b]++;
    }
    topologySort();
}

특징

1. 앞서 말했듯 DAG(Directed Acyclic Graph, 사이클이 없는 방향 그래프)에만 적용이 가능하다.
2. 사이클이 포함된 어떠한 원소도 큐에 들어가지 못하기 때문에 모든 원소를 방문하기 전에 queue가 빈다면 사이클이 존재한다고 판단할 수 있다.
3. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있기 때문에 위상정렬 결과는 여러가지가 존재할 수 있다.
4. 시간복잡도 O(V+E), 차례대로 모든 노드를 확인하면서 (O(V)), 해당 노드에서 출발하는 간선을 차례대로 제거(O(E))

관련 문제

백준 2252번: 줄 세우기, 백준 1516번: 게임 개발 등등