Topology Sort

📝 정의

순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.

예를 들어 다음과 같이 어떠한 일련의 순서가 정해져 있는 task 가 있다고 가정할 때, 이는 조건으로 해석할 수 있다.

🛠 특징

하지만 알고리즘 마스터 과정은 굉장히 다양한 방법이 있기 때문에 다양한 그래프가 나올 수 있다는 것이다.
이 위상 정렬은 여려 개의 답이 존재할 수 있다는 점이 특징이다.
또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용된다.
따라서 시작점이 반드시 명확하게 존재해야한다.

DAG(Directed Acyclic Graph) 란?

이 그래프는 사이클이 발생하지 않는 방향 그래프다.
따라서 사이클이 발생하는 경우는 위상 정렬을 수행할 수 없다.

이 위상정렬은 2가지 해결책을 내는데
1. 현재 그래프는 위상 정렬 가능 여부
2. 위상 정렬 후의 결과

시간 복잡도

위상 정렬의 시간 복잡도는 O(V+E)이다 즉, Votex(정점)의 개수 + Edge(간선)의 개수만큼 소요되므로 매우 빠른 알고리즘이다.

⚙ 동작

1. 진입차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거
3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입.
4. 큐가 빌 때까지 2~3번 과정을 반복.

모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재.
모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과.

진입차수란?

위 그래프에서 BFS 를 배우려면 탐색알고리즘과 Queue 에 대한 개념을 숙지하고 있어야한다. 따라서 BFS 의 진입 차수는 "2" 이다.

문제

1	2	3	4	5	6	7
0	1	1	1	1	2	1

1. 진입차수가 0인 정점을 큐에 삽입
   큐: 1
   출력:

2. 큐에서 원소를 꺼내 연결된 모든 간선 제거
   큐: 2 5
   출력: 1

3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입.
   큐: 5 3
   출력: 1 2

4(2반복). 큐에서 원소를 꺼내 연결된 모든 간선 제거
큐: 3
출력: 1 2 5

...

위상 정렬 결과 출력: 1 2 5 3 4 6 7

💻 코드

큐로 구현하는 것이 일반적으로 더 많이 사용되고 조금 더 고급적인 방법이다.

import java.util.*;

public class TopologySort {
    public static List<Integer> topologySort(int n, List<List<Integer>> edges) {
        // 1-1. 그래프 초기화
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 1-2. 진입 차수 배열 초기화
        int[] inDegree = new int[n + 1];

        // 2. 그래프 구성
        for (List<Integer> edge : edges) {
            int from = edge.get(0);
            int to = edge.get(1);
            graph.get(from).add(to);
            inDegree[to]++;
        }

        // 3. 진입 차수가 0인 노드를 Queue에 추가
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 4. 위상 정렬 수행
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);

            for (int next : graph.get(current)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // 5. 정렬 결과 확인 (사이클이 있으면 실패)
        if (result.size() != n) {
            throw new IllegalStateException("사이클 발생 위상정렬 불가.");
        }

        return result;
    }

    public static void main(String[] args) {
        int n = 7; // 노드의 수
        List<List<Integer>> edges = Arrays.asList(
                Arrays.asList(1, 2),
                Arrays.asList(1, 5),
                Arrays.asList(2, 3),
                Arrays.asList(3, 4),
                Arrays.asList(5, 6),
                Arrays.asList(6, 7),
                Arrays.asList(4, 6)
        );

        try {
            List<Integer> result = topologySort(n, edges);
            System.out.println("Topological Sort: " + result);
        } catch (IllegalStateException e) {
            System.out.println(e.getMessage());
        }
    }
}