[Baekjoon] 23632 쿠키런 킹덤

설명

입력

출력

첫 번째 줄에는 T 초 내에 지을 수 있는 건물의 개수를 출력하고, 두 번째 줄에는 제한 시간 내에 지을 수 있는 모든 건물의 번호를 공백으로 구분하여 오름차순으로 출력한다.

예시 입력

예시 출력

JavaScript
복사

JavaScript
복사

풀이 과정

이 문제는 위상 정렬을 사용하면 쉽게 풀 수 있습니다.

위상 정렬에 대한 내용은 다음 포스팅에서 확인할 수 있습니다. 위상 정렬`

이 문제의 핵심은 각 건물들이 생성할 수 있는 자원이 있다는 점입니다.

따라서 해당 자원을 생성하기 위해서 먼저 지어야 하는 건물들이 존재합니다.

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static boolean[] building, resources;
    static int[] in_degree;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> resource = new ArrayList<>();

    static Queue<int[]> queue = new LinkedList<>();
    static ArrayList<Integer> answer = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        building = new boolean[N + 1];
        resources = new boolean[N + 1];
        in_degree = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            building[Integer.parseInt(st.nextToken())] = true;
        }
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
            resource.add(new ArrayList<>());
        }

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            for (int j = 0; j < a; j++) {
                resource.get(i).add(Integer.parseInt(st.nextToken()));
            }
        }

        for (int i = 0; i < N - M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            in_degree[a] = b;
            for (int j = 0; j < b; j++) {
                graph.get(Integer.parseInt(st.nextToken())).add(a);
            }
        }

        // Initial Setup
        for (int i = 1; i < in_degree.length; i++) {
            if (in_degree[i] == 0) {
                queue.add(new int[]{i, 0});
            }
        }

        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            if (temp[1] > T) {
                break;
            }

            answer.add(temp[0]);
            for (int i = 0; i < resource.get(temp[0]).size(); i++) {
                int res = resource.get(temp[0]).get(i);
                if (resources[res]) {
                    continue;
                }

                resources[res] = true;

                for (int j = 0; j < graph.get(res).size(); j++) {
                    in_degree[graph.get(res).get(j)]--;
                    if (in_degree[graph.get(res).get(j)] == 0) {
                        queue.add(new int[]{graph.get(res).get(j), temp[1] + 1});
                    }
                }

            }
        }

        System.out.println(answer.size());
        Collections.sort(answer);
        for (int i = 0; i < answer.size(); i++) {
            System.out.print(answer.get(i) + " ");
        }
    }
}
JavaScript
복사