P.2623 음악프로그램

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {

    static int n, m;
    static ArrayList<Integer>[] graph;
    static int[] depth;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0];
        m = line[1];
        depth = new int[n + 1];
        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 1; j < line[0]; j++) {
                graph[line[j]].add(line[j + 1]);
                depth[line[j + 1]]++;
            }
        }

        ArrayList<Integer> list = topologicalSort();
        if (list.size() != n) bw.write(Integer.toString(0));
        else {
            for (Integer integer : list) {
                bw.write(integer + "\n");
            }
        }
        bw.flush();
    }

    private static ArrayList<Integer> topologicalSort(){
        LinkedList<Integer> queue = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            if (depth[i] == 0) queue.add(i);
        }

        while (!queue.isEmpty()) {
            Integer poll = queue.poll();

            list.add(poll);

            for (Integer integer : graph[poll]) {
                depth[integer]--;

                if (depth[integer] == 0) queue.add(integer);
            }
        }

        return list;
    }
}

코드 설명

정점을 순서대로 정렬해야 하는 위상정렬 문제다.

핵심 알고리즘은 이 문제와 동일하다.

2023.08.23 - [코딩테스트/백준] - P.1005 ACM Craft

P.1005 ACM Craft

 

저장을 효율적으로 하면 쉽게 풀 수 있는데 예시를 보자.

6 3
3 1 4 3
4 6 2 5 4
2 2 3

첫번째 연결 예시의 경우 1 4 3이다.

이는 다음과 같이 쪼개어 저장했다.

1 4
4 3

1-> 4 -> 3을 1->4와 4->3으로 나눈 것이다.

 

두 번째 연결 예시의 경우 6 2 5 4이다.

다음과 같이 쪼개어 저장한다.

6 2
2 5
5 4

v1, v2 형식을 맞춰주고 graph[v1]에 v2를 저장하고 depth를 v2에 대해서만 증가시킨다.