[Algorithm] 기수 정렬(Topological sort) (BOJ 2252, BOJ 1766)

• Topological sort의 필요

directed acyclic graph(dag)의 경우 가끔씩 순서에 따라 linear한 정렬이 필요한 경우가 있다. 예를 들어 다음과 같은 상황을 가정해 보자.

 

수강할 강의를 선택하려고 한다. 매 학기 하나의 강의만 선택할 수 있고, 어떤 강의는 선수과목이 존재하여 선수강의를 수강하지 않았을 경우 수강할 수 없다. 이 경우 수강할 강의를 선택하는 방법을 제시하라.

위와 같은 상황을 graph로 나타내면 다음과 같을 것이다.

사진 출처 : https://simple.wikipedia.org/wiki/File:Directed_acyclic_graph.svg

맨 처음 선택할 수 있는 과목은 A와 G 뿐이다. A를 수강한 다음이라야 비로소 B를 수강할 수 있고, D를 수강하려면 B와 G를 수강하여야 한다. F 과목을 수강하기 위해서는 F를 제외한 그래프 안의 모든 강의를 수강하여야 한다.

 

이런 문제를 해결하는 경우 직접 모든 정점을 매번 순회하며 수강이 가능한지 확인하는 것은 대단히 비효율적이다. 따라서 이러한 상황을 해결하기 위해 기수 정렬(topological sort)가 필요하다.

 

 

 

 

 

 

 

• topological sort란

topological sort는 directed acyclic graph에 대하여 그 정점들을 순서에 맞게 하나의 horizontal한 line으로 정렬하는 것을 의미한다.

 

• Topological sort는 BFS 기반으로 수행된다 : 

1. in-degree가 0인 vertices를 찾는다.

2. 1의 vectices와, 그에 연결된 edges들을 삭제한다.

3. dag에 남은 vertices가 없을 때까지 1과 2의 과정을 반복한다.

 

• 이는 실용적으로 adjacency list와 queue에 의해서 구현된다.

1. in-degree가 0인 vertices를 찾아 queue에 push한다.

2. queue의 front vertex에 대해서 adjacency list를 탐색하여 연결된 vertices의 in-degree를 1 차감한다.

3. 만약 2에서, 연결된 vertex의 in-degree를 1 차감하였을 경우 0이라면 queue에 push한다.

4. 1-3의 과정을 queue가 empty할 때까지 반복한다.

 

• Time complexity는 O(V+E)로 구현된다. (adjacency list와 queue를 사용하였을 경우)

 

 

• 유의사항

undirected graph나 cyclic graph에서 사용할 수 없다.

 

 

 

 

 

 

• C++에서의 implementation (BOJ 2252)

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

2252번: 줄 세우기

 BOJ 2252는 위상 정렬의 개념을 묻는 아주 간단한 문제이다. 단순히 위상 정렬을 구현하면 된다.

 

for(int i = 1; i<=n; i++) {
    if(degree[i]==0) Q.push(i);
}

 

이처럼 in-degree가 0인 vectices를 queue에 push한다.

 

while(!Q.empty()) {
        int cur = Q.front();
        answer.emplace_back(cur);
        Q.pop();
        for(int i = 0; i< order[cur].size(); i++) {
            int next = order[cur][i];
            degree[next]--;
            if(degree[next]==0) Q.push(order[cur][i]);
        }
    }

 

이후 queue에 원소가 있는 동안 (line 1)

queue의 front에 있는 원소의 adjacency list를 탐색하며 (line5-9)

인접한 vertex들의 in-degree를 1씩 차감해 주고, in-degree가 0이라면 queue에 push한다.(line 8)

 

전체 코드는 내 github에서 확인할 수 있다.

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/2252/2252.cpp

GitHub - Jordano-Jackson/PS: Problem solving

 

 

 

 

 

 

 

• priority_queue를 이용한 implementation (BOJ 1766)

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

1766번: 문제집

 

크게 다를 것 없는 문제지만, queue에 여러 정점이 있을 때, 정점의 번호가 더 작은 것을 먼저 pop해 주기만 하면 된다. 

 

간단하게 생각해 낼 수 있듯이, 이는 priority_queue를 통해서 구현할 수 있다.

 

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

 

위의 코드에서 queue의 선언만 priority queue로 선언하면 된다. 오름차순으로 정렬하기 위해서는 세 번째 인자에 greater<int>를 비교 함수로 전달하면 된다.

 

이 문제의 전체 코드도 내 github에서 확인할 수 있다.

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/1766/1766.cpp

GitHub - Jordano-Jackson/PS: Problem solving

 

 

 

 

 

 

• references

• Cormen, T. H., & Cormen, T. H. (2001). Introduction to algorithms. Cambridge, Mass: MIT Press.