[백준] 2623 음악프로그램 - Java

 

 

문제 출저 

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

2623번: 음악프로그램

 

 

 

문제 풀이

가수의 순서가 들어오고 이 순서들을 모두 만족하는 순서를 구해야 합니다. 또한 모두 만족할 수 없을 경우 0을 출력해야 합니다.

 

위상 정렬로 풀었습니다. 

가수들의 순서를 입력받을 때 가수의 간선 정보와 앞에 몇 명의 가수가 와야하는지를 저장했습니다.

 

만족하지 못 했을 경우는 사이클을 구하는 방식으로 구했습니다.

사이클의 형성은 총 갯수 N이 아닌 경우 입니다. 

만약 1 3   /   3 1 로 입력이 들어온 경우 1 -> 3 -> 1 로 사이클이 형성됩니다.

 

 

 

 

 

소스 코드

package baekjoon.backjoon9.day26;


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

/*
음악프로그램
https://www.acmicpc.net/problem/2623
 */
public class B2623 {

    static int n, m;

    static int[] need;
    static List<Integer>[] orderList;



    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());

        need = new int[n+1];
        orderList = new List[n+1];
        for(int i = 0; i < n+1; i++) {
            orderList[i] = new ArrayList<>();
        }


        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int num = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());

            for(int j = 1; j < num; j++) {
                int end = Integer.parseInt(st.nextToken());
                need[end] += 1;
                orderList[start].add(end);
                start = end;
            }
        }


        Queue<Integer> que = new LinkedList<>();
        for(int i = 1; i < n+1; i++) {
            if(need[i] == 0) {
                que.add(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        int count = 0;
        while (!que.isEmpty()) {
            Integer p = que.poll();

            count++;
            sb.append(p).append("\n");

            for(int data : orderList[p]) {
                need[data] -= 1;

                if(need[data] == 0) {
                    que.add(data);
                }
            }
        }
        
        // 불가능 : 사이클 확인 1 -> 3 -> 1 같은 경우
        if(count != n) {
            System.out.println(0);
            return;
        }

        System.out.println(sb);



    }

}