[Algorithm] 위상 정렬

위상 정렬 (Topological Sorting)

위상 정렬이란?

• 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
• 쉽게 말하자면, 순서가 정해져 있는 작업을 정렬 할 때 사용할 수 있는 알고리즘이다.

정의만으로는 무슨 의미인지 파악하기 힘들다.
예시 사진을 보자.

사진과 같이 1부터 6까지의 노드가 있고, 방향성이 있는 간선이 각각 존재한다.
위상 정렬 알고리즘을 구현하기 위해 다음과 같은 과정만 지키면 된다.

1. 진입차수가 0인 노드를 큐에 모두 넣는다.
2. 큐에서 노드(V1)를 하나 꺼낸다.
3. V1에 연결 된 모든 노드를 순회한다.
4. 노드(V2) 발견 시, 간선을 제거 한다.
5. V2의 진입차수를 1 감소 시킨다.
6. V2의 진입차수가 0이면 큐에 넣는다

예시 문제를 보고 위상 정렬을 익혀보겠다.

예시 문제

백준 - 줄 세우기

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 
마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 
그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 
다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 
이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

예제 입력

3 2
1 3
2 3

예제 출력

1 2 3

학생들의 키 순서가 주어졌고, 정해진 순서를 지켜가며 정렬을 해주면 되기에 위상 정렬을 사용하면 된다.

코드

import java.util.*;
import java.io.*;

public class Baek_2252 {
    public static void main (String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Queue<Integer> queue = new LinkedList<>();

        ArrayList<Integer>[] graph = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        int[] indegrees = new int[n + 1];

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(bf.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph[from].add(to);
            indegrees[to]++;
        }

        for(int i = 1; i <= n; i++) {
            if(indegrees[i] == 0) {
                queue.offer(i);
            }
        }

        while(!queue.isEmpty()) {
            int now = queue.poll();
            sb.append(now).append(" ");

            int size = graph[now].size();
            for(int i = 0; i < size; i++) {
                int node = graph[now].get(0);
                indegrees[node]--;
                if(indegrees[node] == 0) {
                    queue.offer(node);
                }
                graph[now].remove(0);
            }
        }
        System.out.println(sb.toString());
    }
}

출처

1. 위키 백과
2. kdb.velog
3. LeetCode