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

문제

www.acmicpc.net/problem/2623

2623번: 음악프로그램

문제해결방법

이 문제는 정해진 순서를 지키면서 가수들의 출연 순서를 정하는 문제였고 위상 정렬을 이용해서 풀었다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main2623_음악프로그램 {
 
    public static int N, M;
    public static int[] v;
    public static List<Integer>[] list;
    public static Queue<Integer> q = new ArrayDeque<>();
 
    public static void bfs(int index) {
        Queue<Integer> bfsq = new ArrayDeque<>();
        bfsq.add(index);
        q.add(index);
        v[index]--;
        while(!bfsq.isEmpty()) {
            int cur = bfsq.poll();
            for(int i=0; i<list[cur].size(); i++) {
                int next = list[cur].get(i);
                v[next]--;
                if(v[next]==0) {
                    bfsq.add(next);
                    q.add(next);
                    v[next]--;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        v = new int[N+1];
        list = new List[N+1];
        for(int i=1; i<=N; i++) list[i] = new ArrayList<Integer>();
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            int before = Integer.parseInt(st.nextToken());
            for(int j=1; j<c; j++) {
                int cur = Integer.parseInt(st.nextToken());
                v[cur]++;
                list[before].add(cur);
                before = cur;
            }
        }
        for(int j=1; j<=N; j++) {
            if(v[j]==0) {
                bfs(j);
            }
        }
        boolean flag = false;
        for(int j=1; j<v.length; j++) {
            if(v[j]>0) {
                flag = true;
                break;
            }
        }
        if(flag) System.out.println("0");
        else {
            while(!q.isEmpty()) System.out.println(q.poll());
        }
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.