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

1.  문제 링크

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

2.  문제

요약

• 남일이는 '뮤직 KOI'에서 가수의 출연 순서를 정하는데, 이를 정하기 위해서 많은 조건을 따져야 합니다.
• 예를 들어, 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였고 다음과 같습니다.
  • 1 4 3
  • 6 2 5 4
  • 2 3
• 첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했고 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로, 세 번째 보조 PD는 2번 먼저, 다음에 3번으로 순서를 정했습니다.
• 한 가수를 여러 보조 PD가 담당할 수도 있습니다.
• 남일이는 이 순서들을 모아 6 2 1 5 4 3으로 전체 가수의 순서를 정했습니다. 이는 세 보조 PD가 정해온 순서를 모두 만족하는 경우입니다.
• 경우에 따라서 남일이가 모두를 만족하는 순서를 정하는 것이 불가능할 수도 있습니다.
• 보조 PD들이 만든 순서들이 주어질 때, 전체 가수의 순서를 정하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 가수의 수 N과 1보다 크거나 같고 100보다 작거나 같은 보조 PD의 수 M이 주어지고 두 번째 줄부터 M개의 줄에서 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 가수들의 순서가 주어집니다.
  • 가수는 번호 1, 2, ..., N으로 표시합니다.
• 출력: N개의 줄에 남일이가 정한 가수들의 출연 순서를 한 줄에 하나의 번호로 출력합니다. 답이 여러 개일 경우 아무거나 하나를 출력합니다. 만약 남일이가 순서를 정하는 것이 불가능한 경우라면 첫 번째 줄에 0을 출력합니다.

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N, M;
    static int[] related;
    static HashMap<Integer, HashSet<Integer>> followings, precede; // 후행, 선행되어있는 것들
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        M = scanner.nextInt();
        related = new int[N + 1];
        followings = new HashMap<>();
        precede = new HashMap<>();
        for(int singer = 1; singer <= N; singer++) {
            followings.put(singer, new HashSet<>());
            precede.put(singer, new HashSet<>());
        }
        for(int idx = 0; idx < M; idx++) {
            int num = scanner.nextInt();
            int singer = scanner.nextInt();
            ArrayList<Integer> list = new ArrayList<>(Arrays.asList(singer));
            for(int s = 1; s < num; s++) {
                singer = scanner.nextInt();
                for(int pre : list) {
                    precede.get(singer).add(pre);
                    followings.get(pre).add(singer);
                }
                list.add(singer);
            }
        }
    }

    static void solution() {
        Queue<Integer> queue = new LinkedList<>();
        LinkedList<Integer> answer = new LinkedList<>();
        int[] related = new int[N + 1];
        for(int key : precede.keySet()) {
            related[key] = precede.get(key).size();
            if(related[key] == 0) {
                queue.offer(key);
                answer.add(key);
            }
        }
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            for(int singer : followings.get(cur)) {
                related[singer]--;
                if(related[singer] == 0) {
                    queue.offer(singer);
                    answer.add(singer);
                }
            }
        }
        if(answer.size() == N) {
            for(int singer : answer) sb.append(singer).append('\n');
        } else sb.append(0).append('\n');
        System.out.println(sb);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader((System.in)));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch(IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}