[백준 2623] 음악프로그램(Java)

문제 링크 : https://www.acmicpc.net/problem/2623

이 문제는 위상 정렬을 이용해서 풀 수 있습니다. 각 보조 PD들이 준 명단끼리 순서가 존재할 때 전체 순서를 구해야 하고 사이클이 존재하지 않기 때문에 위상 정렬을 사용할 수 있습니다. 여기서 주의할 점은 입력받은 순서대로 이전값과 현재값이 연결되기 때문에 값을 입력받을 때 이전값을 기록하면서 현재값 입력이 끝나면 이전값을 현재값으로 변환하는 방식으로 진행하면 됩니다.

다음은 코드입니다.

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

class Main{
    static int N,M;
    static List<Integer>[] graph;
    static int[] map;

    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());

        graph = new List[N+1];
        for(int i=0;i< graph.length;i++) graph[i] = new ArrayList<>();
        map = new int[N+1];

        for(int i=1;i<=M;i++){
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int before = Integer.parseInt(st.nextToken());
            for(int j=1;j<n;j++){
                int curr = Integer.parseInt(st.nextToken());
                graph[before].add(curr);
                map[curr]++;
                before = curr;
            }
        }

        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        for(int i=1;i<=N;i++) if(map[i]==0) queue.add(i);

        while(!queue.isEmpty()){
            int curr = queue.poll();
            res.add(curr);
            for(int next : graph[curr]){
                map[next]--;
                if(map[next]==0) queue.add(next);
            }
        }

        if(res.size()!=N) System.out.println("0\n");

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<res.size();i++) sb.append(res.get(i)).append("\n");
        System.out.println(sb);
    }
}