백준 2252번 : 음악프로그램 java

이 문제는 위상 정렬을 이용하여 그래프 구조로 되어 있는 자료들을 배열의 형태로 나타내는 문제입니다.

위상 정렬에 관련된 내용들은 아래에 있는 링크를 참고하시면 이해하실 수 있으실 겁니다.

백준 2252번 : 줄 세우기 java

이 문제는 위의 문제와 거의 유사한 형태의 문제입니다.

위상 정렬에 대한 풀이만 이해하시면 위의 문제를 해결하실 수 있으실 겁니다.

---

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

public class Main {
    static int N;
    static List<List<Integer>> l = new ArrayList<>();
    static int[] parentNum;
    static int[] answer;

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

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

        parentNum = new int[N+1];
        answer = new int[N];

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

        while(M-->0){
            st = new StringTokenizer(br.readLine());

            int cnt = Integer.parseInt(st.nextToken());
            int exNum = Integer.parseInt(st.nextToken());

            for(int i = 1; i<cnt; i++){
                int num = Integer.parseInt(st.nextToken());

                l.get(exNum).add(num);
                parentNum[num]++;

                exNum = num;
            }
        }

        findOrder();

        for(int i = 0; i<N; i++) {
            if (answer[i] == 0) {
                System.out.println(0);
                return;
            }
        }

        for(int i = 0 ; i<N; i++)
            System.out.println(answer[i]);
    }

    static void findOrder() {
        Queue<Integer> q = new LinkedList<>();
        int answerIdx = 0;

        for (int i = 1; i <= N; i++)
            if(parentNum[i] == 0) {
                q.offer(i);
                answer[answerIdx++] = i;
            }

        while(!q.isEmpty()){
            int num = q.poll();

            for(int i = 0; i<l.get(num).size(); i++){
                int nextNum = l.get(num).get(i);

                parentNum[nextNum]--;
                if(parentNum[nextNum] == 0){
                    q.offer(nextNum);
                    answer[answerIdx++] = nextNum;
                }
            }
        }
    }
}