[알고리즘] 위상 정렬

위상 정렬은 선행 관계가 정해진 작업들 사이에서, 모든 제약을 만족하는 실행 순서를 찾는 알고리즘이다.

예를 들어,

• 배럭 -> 팩토리 -> 스타포트 -> 사이언스 퍼실러티
• 팩토리 -> 머신샵 -> 탱크
• 스타포트 -> 레이스

가 주어질때, 모든 연구를 다 할수 있는 순서는

• 배럭 -> 팩토리 -> 머신샵 -> 탱크 -> 스타포트 -> 레이스 -> 사이언스 퍼실러티

이렇게 정렬할 수 있다. (물론 다른 경우의 수도 가능하다)

보다시피 사이클이 발생하면 안된다. 위상 정렬 알고리즘의 조건은, 방향 비순환 그래프(directed acyclic graph, DAG)이다.

아이디어

위상 정렬의 핵심 아이디어는 진입 차수 이다.
진입 차수란, 특정 작업을 시작하기 전에 선행되어야 할 작업의 개수를 의미한다.

위상 정렬 알고리즘은 다음과 같은 흐름으로 동작한다.

1. 진입 차수가 0인 작업 (선행 조건이 없는 작업) 부터 시작한다
2. 해당 작업을 선행 조건으로 갖는 작업들의 진입 차수를 1씩 줄인다.
3. 새롭게 진입 차수가 0이 된 작업으로 위 과정을 반복한다
4. 진입 차수가 0이 되는 순서대로 작업을 나열하면 전체 작업의 가능한 실행 순서를 알 수 있다

위상 정렬 알고리즘 흐름 (kahn's algorithm)

이번엔 알고리즘 관점에서 흐름을 그려보자.

1. 주어진 작업의 조건들을 그래프로 표현한다.
2. 진입 차수 배열 생성
   • 모든 작업의 진입 차수(둘어오는 간선 수)를 계산한다.
3. 진입 차수가 0인 작업들을 큐에 삽입한다.
4. 큐가 빌 때까지 다음 작업을 반복한다
   • 큐에서 노드를 하나 꺼낸다.
   • 해당 노드를 결과 리스트에 추가한다.
   • 꺼낸 노드에서 연결된 노드들의 진입 차수를 1씩 감소시키고, 나가는 간선을 모두 제거한다.
   • 진입 차수가 0이 된 노드를 큐에 삽입한다.
5. 결과 리스트가 정답이 된다.
   • 결과 리스트의 크기가 노드 수와 다르면 위상 정렬이 불가능한 것이다.

시간 복잡도

우선 모든 정점을 순회하고, 모든 간선의 개수만큼 순회하므로 $O(V+E)$ 이다.

예시 문제

백준 1005 - ACM Craft
백준 2623 - 음악프로그램

코드

2623번의 코드이다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        List<List<Integer>> graph = new ArrayList<>();
        int[] indegree = new int[N + 1]; // 진입 차수 배열

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            int count = sc.nextInt();
            int[] sequence = new int[count];

            for (int j = 0; j < count; j++) {
                sequence[j] = sc.nextInt();
            }

			// 그래프 및 진입 차수 초기화
            for (int j = 0; j < count - 1; j++) {
                int from = sequence[j];
                int to = sequence[j + 1];
                graph.get(from).add(to);
                indegree[to]++;
            }
        }

        // 위상 정렬 시작 (Kahn's algorithm)
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

		// 진입 차수가 0인 노드 찾기
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            result.add(curr);

            for (int next : graph.get(curr)) {
	            // 꺼낸 노드에서 연결된 노드들의 진입 차수를 1씩 감소
                indegree[next]--; 
                
                // 진입 차수가 0이 된 노드를 큐에 삽입한다.
                if (indegree[next] == 0) { 
                    queue.offer(next);
                }
                // 0이 되는 순간에만 진입 차수가 0이 되는걸 체크하므로, 간선을 제거하지 않아도 된다.
            }
        }

        if (result.size() == N) {
            for (int num : result) {
                System.out.println(num);
            }
        } else { // 결과 리스트의 크기가 노드 수와 다르면 위상 정렬이 불가능한 것이다.
            System.out.println(0);
        }
    }
}

참고: Kahn's Algorithm 말고도 DFS 기반 방식도 있다.