[알고리즘] 위상 정렬

위상 정렬(Topological Sort)이란?

방향성이 있는 그래프(Directed Acyclic Graph, DAG)에서 선행 관계를 유지하면서 모든 노드를 순서대로 나열하는 방법

즉, 어떤 일을 수행하는 순서가 있을 때 그 순서를 결정하는 알고리즘

 

예시 : 특정 작업이 끝나야만 다른 작업이 가능할 때

 

 

 

위상 정렬을 알기 전 알아야 할 지식

진입 차수(indegree) : 특정 노드로 들어오는 간선의 개수

진출 차수(outdegree)  : 특정 노드에서 나가는 간선의 개수

 

 

위상 정렬 알고리즘 동작 과정

위상 정렬 알고리즘은 큐를 사용하여 구현을 합니다.

1. 진입 차수가 0인 노드를 큐에 넣습니다.
2. 큐가 빌 때까지 다음 과정을 반복합니다.
   • 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   • 새롭게 진입 차수가 0이 된 노드를 큐에 삽입

 

 

예제 https://www.acmicpc.net/problem/2623

백준 : 음악프로그램

 

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static List<List<Integer>> graph = new ArrayList<>();

    static int N;
    static int M;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        // 각 노드별 진입차수를 저장할 배열
        int[] indegree = new int[N+1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int num = Integer.parseInt(st.nextToken());
            int before = Integer.parseInt(st.nextToken());

            for (int j = 1; j < num; j++) {
                int singer = Integer.parseInt(st.nextToken());
                graph.get(before).add(singer);
                
                // 이전 노드의 진출 차수이며 현재 singer의 진입 차수
                indegree[singer]++;
                before = singer;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

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


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

            // 현재(now) 노드의 진입 차수를 모두 - 1씩 하며 0이 된 노드는 큐에 삽입
            for (int next : graph.get(now)) {
                indegree[next]--;

                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }


        if (result.size() != N) {
            System.out.println(0);
            return;
        }


        for (int singer : result) {
            sb.append(singer).append("\n");
        }

        System.out.println(sb);
    }
}