[Coding Test] inflearn(13)

1. 위상 정렬 (topology sort)

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.

위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 또한, 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.

위상 정렬의 원리

1. 우선 진입 차수를 이해해야 한다. 진입 차수 (in-degree)는 자기 자신을 가리키는 에지의 개수이다.
   다음을 보면 ArrayList로 그래프를 표현했다. 그래프는 사이클이 없는 상태이다.
   
   진입 차수 배열 D를 다음과 같이 업데이트를 한다. 1에서 2, 3을 가리키고 있으므로 D[2], D[3]를 각각 1만큼 증가시킨다.
   
2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.
   
   위의 그림의 경우 진입 차수가 0인 노드 1을 선택하여 2, 3의 진입 차수를 1씩 빼 D[2], D[3]을 0으로 만든 것이다. 계속해서 다음 노드 2를 선택하여 반복한다. 이 과정을 모든 노드가 정렬될 때까지 반복한다. 여기서 진입 차수가 0인 노드를 3을 먼저 선택했다면 3이 우선 위상 정렬 배열에 들어갈 것이다. 앞서 위상 정렬이 늘 같은 정렬 결과를 보장하지 않는다고 말했던 것이 바로 이런 경우를 말한다.
   
   위상 정렬 결과는 다음과 같다.
   

2. 위상 정렬 실전 문제

줄 세우기 (백준 2252)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P2252_줄세우기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        ArrayList<Integer>[] al = new ArrayList[N + 1];
        int[] sorted = new int[N + 1];
        for (int i = 1; i <= N; i++) al[i] = new ArrayList<Integer>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            al[a].add(b);
            sorted[b]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (sorted[i] == 0) queue.add(i);
        }
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            int num = queue.poll();
            sb.append(num + " ");
            for (int i = 0; i < al[num].size(); i++) {
                sorted[al[num].get(i)]--;
                if (sorted[al[num].get(i)] == 0) queue.add(al[num].get(i));
            }
        }
        System.out.println(sb);
    }
}