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

1. 문제 링크

2623번: 음악프로그램

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. PD의 수만큼 ArrayList를 만든다.

2. 입력받은 순서대로 list에 넣으면서 진입차수를 더해준다. 3. 위상정렬을 진행한다.

    3-1. 처음에 진입차수가 0인(선행되는 수가 없는) 숫자를 큐에 넣는다.

    3-2. 큐에서 빼고 결과 list에 추가한다.

    3-3. 그 수와 연결된 숫자들의 진입차수를 하나씩 빼면서 0이 될 때 큐에 넣는다.

4. 위상 정렬이 끝난 후 결과 list에 N개가 전부 들어왔다면 위상정렬이 성공된 것이다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;

public class Main {
    static int N, in[];
    static ArrayList<Integer>[] list;
    static ArrayList<Integer> result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] split = br.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        int M = Integer.parseInt(split[1]);

        in = new int[N+1];
        list = new ArrayList[N+1];
        result = new ArrayList<>();

        for(int i=0;i<N+1;i++){
            list[i] = new ArrayList<>();
        }

        for(int i=0;i<M;i++){
            split = br.readLine().split(" ");
            int num = Integer.parseInt(split[0]);
            int first = Integer.parseInt(split[1]);
            for(int j=2;j<num+1;j++){
                int next = Integer.parseInt(split[j]);
                list[first].add(next);
                in[next]++;
                first = next;
            }
        }

        topology(); //위상정렬

        // N개가 위상정렬되었음
        if(result.size() == N){
            for(Integer i: result) {
                sb.append(i).append("\n");
            }
            System.out.println(sb);
        }
        else{
            System.out.println(0);
        }

    }

    private static void topology() {
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i < N + 1; i++) {
            if (in[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int now = queue.poll();
            result.add(now);
            for (Integer i : list[now]) {
                if (--in[i] == 0) {
                    queue.offer(i);
                }
            }
        }
    }
}