[알고리즘] 위상 정렬(Topological Sort) - 개발하는 지토

위상 정렬(Topological Sort)

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

즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 이다.

위상 정렬을 가장 잘 설명할 수 있는 예시는 대학의 선수과목 구조 또는 게임에서의 스킬트리 중 선행스킬이 존재하는 경우이다.

앞선 대표 예 두가지 중 각자 더 이해가 쉬운 예시를 떠올려 보면 쉽게 이해할 수 있을 것이다.

위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다. 즉, 비순환 방향 그래프(Directed Acyclic Graph, DAG) 여야 한다. 그리고 하나의 방향 그래프에 대해서 위상 정렬을 수행한 결과 값이 여러개가 나올 수 있다.

위상 정렬 (Java)

import java.util.*;

public class TopologicalSort {
    // 노드의 개수(v), 그래프 간선의 개수 (e)
    public static int v;
    // 모든 노드에 대한 진입차수를 기록할 배열
    public static int[] indegree;
    // 각 노드에 연결된 간선 정보를 담기 위한 리스트 초기화
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    // 위상 정렬
    public static void topologySort() {
        Queue<Integer> q = new LinkedList<>(); // 큐 라이브러리 사용

        // 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
        for (int i = 1; i <= v; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        // 큐가 빌 때까지 반복
                while (!q.isEmpty()) {
            // 큐에서 원소 꺼내기
            int now = q.poll();

                        // 순서를 출력하려면, now를 출력
                        System.out.println(now);

            // 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            for (int next : graph.get(now)) {
                inDegree[next]--;
                // 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
                if (inDegree[next] == 0) {
                                    q.offer(next);
                                }
            }
        }
    }

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

        v = sc.nextInt();
                indegree = new int[v+1];

        // 그래프 초기화
        for (int i = 0; i <= v; i++) {
            graph.add(new ArrayList<>());
        }

        // 방향 그래프의 모든 간선 정보를 입력받기 (a -> b)
        for (int i = 0; i < e; i++) {
            a = sc.nextInt(); // 선행
            b = sc.nextInt(); // 후행
            graph.get(a).add(b);
            indegree[b]++ // 후행 노드의 진입 차수 + 1
        }

        topologySort();
    }
}

코드 설명 (Step)

1. 진입 차수가 0인 정점을 큐에 추가한다. (선행 조건이 없는 정점부터)
2. 큐에 저장된 정점을 하나 꺼낸다.
3. 꺼낸 정점과 연결된 정점을 찾고, 선행 조건인 정점이 처리 되었으므로 연결된 정점의 진입 차수를 하나 빼준다.
4. 연결된 정점의 진입 차수가 0이라면(선행 조건 없음) 해당 정점을 큐에 추가한다.
5. 큐가 빌 때 까지 2 ~ 4 번의 과정을 반복한다.

문제

14567 - 선수과목

2056 - 작업

1516 - 게임 개발

2252 - 줄 세우기

3665 - 최종 순위