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

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

2623번: 음악프로그램

 

🐢문제설명

대표적인 위상정렬 문제이다. 각 pd별로 원하는 순서가 있고 모든 pd의 요구사항에 맞는 순서대로 가수를 줄세워야 한다. 이를 위해서는 의존관계를 명시해주기 위해서 인접리스트와 진입차수를 위한 배열을 사용하면 된다.

 

인접리스트이 용도는 A가수가 부르고 난 후 다음에 부를 수 있는 B가수를 이어주기 위한 용도이고, 진입 차수는 자신 앞에 선행되어야 할 가수의 수를 적어주기 위한 용도이다.

 

따라서, 먼저 진입차수가 0인 요소부터 순서를 보장하기 위해 Queue에 담고, 해당 가수들 부터 뽑아서 부른 후 해당 가수 뒤에 연결된 가수들의 진입 차수를 1씩 줄여준다. 줄여준 차수가 0이되면 해당 가수도 부를수 있게 된 것이므로 Queue에 담아준다.

 

결과적으로 Queue가 빌때까지 진행되고 완료된 후 부른 모든 가수들의 수가 기존에 제안된 가수들의 수와 동일하다면 가능한 경우이므로 순서대로 뽑아주면 된다.

 

🐢코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, K;
    static ArrayList<Integer>[] songAdj;
    static int[] degree;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input;
 
        input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]) + 1;
        K = Integer.parseInt(input[1]);
 
        degree = new int[N]; // 진입차수
        songAdj = new ArrayList[N]; // 인접 리스트
        for (int i = 0; i < N; i++) {
            songAdj[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < K; i++) {
            input = br.readLine().split(" ");
            int len = Integer.parseInt(input[0]);
            for (int song = 1; song < len; song++) {
                int nowSong = Integer.parseInt(input[song]);
                int nextSong = Integer.parseInt(input[song + 1]);
                songAdj[nowSong].add(nextSong); // 현재가수 -> 다음가수 -> ...
                degree[nextSong] += 1; // 차수 증가
            }
        }
 
        List<Integer> answer = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < N; i++) {
            if (degree[i] == 0) queue.add(i); // 차수가 0인 가수부터 부른다
        }
 
        while (!queue.isEmpty()) {
            int nowSong = queue.poll();
            answer.add(nowSong);
            for (int nextSong : songAdj[nowSong]) {
                degree[nextSong] -= 1; // 차수를 줄여주고 0이면 큐에 담아준다
                if (degree[nextSong] == 0) queue.add(nextSong);
            }
        }
 
        StringBuilder result = new StringBuilder();
        if (answer.size() == N - 1) { // 가수 수가 동일한 경우 정상적으로 된 것
            for (int song : answer)
                result.append(song).append("\n");
            System.out.println(result);
        } else System.out.println(0);
    }
}