[백준, Java] 2623번 : 음악프로그램

🔗 문제 링크

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

😮 문제 해결 방법

위상 정렬을 이용해 서로의 순서를 구해준다.

1. 입력에 대해 그래프를 생성한다.
2. 입력에 대해 순서에 따라 indegree 배열의 개수를 카운팅해준다.
3. 위상 정렬을 이용해 순서를 리스트에 담아준다.
   1. 리스트 사이즈가 N보다 작은 경우 순서를 보장할 수 없는 경우 → 0을 반환
   2. 그 외 순서 리스트를 반환해 출력한다.

🚩 Java 코드

package com.second.algorithm.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_2623_음악프로그램 {
    private static int N, M;
    private static List<List<Integer>> graph;

    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());
        M = Integer.parseInt(st.nextToken());
        graph = new ArrayList<>();

        int[] indegree = new int[N + 1];
        for (int index = 0; index <= N; index++) {
            graph.add(new ArrayList<>());
        }

        // 순서 정보 저장
        for (int pd = 0; pd < M; pd++) {
            st = new StringTokenizer(br.readLine());
            int singerCount = Integer.parseInt(st.nextToken());
            int singer = 0;
            for (int index = 0; index < singerCount; index++) {
                int nextSinger = Integer.parseInt(st.nextToken());

                if (singer != 0) {
                    graph.get(singer).add(nextSinger);
                    indegree[nextSinger]++;
                }
                singer = nextSinger;
            }
        }

        int[] rst = startMusicBank(indegree);
        Arrays.stream(rst).forEach(System.out::println);
        br.close();
    }

    private static int[] startMusicBank(int[] indegree) {
        Queue<Integer> queue = new LinkedList<>();
        for (int singer = 1; singer <= N; singer++) {
            if (indegree[singer] == 0) queue.add(singer);
        }

        List<Integer> orders = new ArrayList<>();

        // 위상 정렬 시작
        while (!queue.isEmpty()) {
            Integer singer = queue.poll();
            orders.add(singer);
            for (Integer nextSinger : graph.get(singer)) {
                indegree[nextSinger]--;
                if(indegree[nextSinger] == 0) {
                    queue.add(nextSinger);
                }
            }
        }

        if(orders.size() < N) return new int[]{0};  // 모든 가수의 순서가 정해지지 않은 경우 = size가 N 보다 작은 경우
        return orders.stream().mapToInt(Integer::intValue).toArray();   // List to Array
    }
}