[BOJ] [JAVA] [GOLD 3] 2623: 음악프로그램

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static Node adjList[];
    static int inDegree[];
    static class Node {
        int vertex;
        Node link;

        public Node (int vertex, Node link){
            this.vertex = vertex;
            this.link = link;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 가수의 수
        M = Integer.parseInt(st.nextToken()); // 보조PD의 수
        
        adjList = new Node[N+1];
        inDegree = new int[N+1]; // 진입 간선의 수 체크

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken()); // 보조PD가 담당한 가수의 수
            int temp[] = new int[num];
            for (int i = 0; i < num; i++) {
                temp[i] = Integer.parseInt(st.nextToken()); // 순서
            }
            for (int i = 0; i < num-1; i++) {
                // A -> B
                int A = temp[i]; // 진출 정점
                int B = temp[i+1]; // 진입 정점
                adjList[A] = new Node(B, adjList[A]);
                inDegree[B]++; // 진입 간선++
            }
        }

        ArrayList<Integer> list = topologySort();
        if(list.size() == N) {
            for (Integer vertex : list) System.out.println(vertex);
        } else {
            System.out.println(0);
        }
    }

    private static ArrayList<Integer> topologySort() {
        ArrayList<Integer> orderList = new ArrayList<>();
        Queue<Integer> q = new ArrayDeque<>();

        for (int i = 1; i <= N; i++) {
            if(inDegree[i] == 0) q.offer(i); // 진입 차수가 0인 애들 넣어주고
        }

        while(!q.isEmpty()) {
            int cur = q.poll();
            orderList.add(cur);

            // 현재 정점 기준으로 인접정점 정리
            for (Node node = adjList[cur]; node != null; node = node.link) {
                if(--inDegree[node.vertex] == 0) q.offer(node.vertex);
            }
        }
        return orderList;
    }
}

위상 정렬

• 유향 그래프
• 싸이클 존재하지 않음
• 방향성을 거스리지 않으면서 순서적으로 탐색

• 메커니즘
  • 차수 - 정점에 연결된 간선 수
    • 진출 차수 - 자신의 정점에서 타정점으로 나가는 간선 수
    • 진입 차수 - 타정점에서 자신의 정점으로 들어오는 간선 수
  1. • •  
       1. 진입 차수가 0인 노드(시작점)를 큐에 모두 넣는다.
       2. 큐에서 진입 차수가 0인 노드를 꺼내어 자신과 입전한 노드의 간선을 제거한다.
          1. 인접한 노드의 진입 차수를 1 감소시킨다.
       3. 간선 제거 후 진입 차수가 0이 된 노드를 큐에 넣는다.
       4. 큐가 공백 큐 상태가 될 때 까지 2-3 작업을 반복
          1. 모든 노드가 처리되지 않았다면 사이클 발생
          2. 모든 노드가 다 처리되었다면 위상 정렬 완성