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

문제 설명

• https://www.acmicpc.net/problem/2623
• Gold 3
• 소요 시간 : 15분

문제 풀이

• 위상 정렬을 이용하여 풀이하였다.
• 입력에서 각 노드의 진입차수와 그래프(간선 : 이전가수->다음가수)를 정해준다.
• 해당 데이터를 바탕으로 위상정렬을 진행하되 결과의 크기가 N이 아니면 사이클 존재, 0출력.

소스 코드 (JAVA)

import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class Main {
    static int N, M;
    static List<Integer>[] map;
    static int[] inDegree;

    static void solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new List[N+1];
        inDegree = new int[N+1];
        for (int i = 0; i <= N; i++)
            map[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int before = 0;
            for (int j = 0; j < n; j++) {
                int cur = Integer.parseInt(st.nextToken());
                if (before == 0) {
                    before = cur;
                    continue;
                };
                inDegree[cur]++;
                map[before].add(cur);
                before = cur;
            }
        }

        //위상 정렬 진행
        Queue<Integer> q = new ArrayDeque<>();
        Queue<Integer> res = new ArrayDeque<>();
        for (int i = 1; i <= N; i++)
            if (inDegree[i] == 0) q.add(i);
        while(!q.isEmpty()) {
            int cur = q.poll();
            res.add(cur);
            for (int next : map[cur]) {
                if (--inDegree[next] == 0) {
                    q.add(next);
                }
            }
        }

        if (res.size() == N) {
            for (int num : res)
                bw.write(num + "\n");
        } else {
            bw.write("0\n");
        }

        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        solve();
    }
}

/**
 * 음악 프로그램 (12:00)
 *
 * - N : 가수의 수 ( N <= 1000)
 * - M : PD의 수  ( M <= 100)
 *
 * - 위상 정렬
 * - 각 순서대로 노드를 연결시키고 inDegree 배열을 정의
 *
 * N M
 * n 1 2 3 4
 * ...
 */