[JAVA]백준 1516번: 게임 개발

www.acmicpc.net/problem/1516

1516번: 게임 개발

 

1. 문제 설명

 

어떤 건물을 짓기 전에 그 건물을 짓기 전에 지어야 하는 건물들을 지은 후에 지을 수 있다. 여러 개의 건물을 동시에 지을 수 있고, 건물을 짓는 명령을 내리기까지 시간이 걸리지 않는다고 하고,

 

각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어질 때, 각 건물이 완성되기까지 걸리는 최소 시간을 출력하는 문제이다.

 

2. 풀이

 

백준 2056번 작업과 유사한 문제이다. 위상 정렬에 대해서 알지 못한다면 먼저 문제를 풀어보는걸 추천한다.

kwoncorin.tistory.com/76

[JAVA]백준 2056번: 작업

작업 문제와 다른 점은 작업 문제에서는 현재 작업을 수행하기 전에 완료되어야 하는 작업들의 번호가 현재 작업의 번호보다 작았다. 현재 작업의 번호가 K라고 하면 이전에 수행되어야 하는 작업들은 1 이상 K-1이하의 번호를 가졌다. 하지만 이번 문제에서는 그러한 조건이 없기에 다이나믹 프로그래밍으로만 푸는 것보다는 위상정렬로 푸는 것이 더 효율적이다.

 

 

dp[X]=Math.max(dp[X],time[X]+dp[이전건물])

현재 건물 X를 짓는데 걸리는 최소시간은 현재 건물 X를 짓기 위해 이전에 지어야 하는 건물들을 짓기까지의 시간과 현재 건물 X를 짓는데만 걸리는 시간의 최댓값이다.

 

이러한 식과 위상 정렬을 이용하면 쉽게 풀 수 있다.

 

 

 

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {


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

        int building_num;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        building_num = Integer.parseInt(br.readLine());

        int[] time = new int[building_num + 1];
        int[] dp = new int[building_num + 1];
        int[] in = new int[building_num + 1];
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        for (int x = 0; x <= building_num; x++) {
            list.add(new ArrayList<>());
        }

        for (int x = 1; x <= building_num; x++) {

            StringTokenizer input = new StringTokenizer(br.readLine());

            int size = input.countTokens() - 1;

            time[x] = Integer.parseInt(input.nextToken());

            for (int y = 1; y < size; y++) {

                int pre = Integer.parseInt(input.nextToken());

                list.get(pre).add(x);

                in[x]++;
            }

        }

        for (int x = 1; x <= building_num; x++) {
            if (in[x] == 0) {
                dp[x] = time[x];
                queue.add(x);
            }
        }

        while (!queue.isEmpty()) {

            int now = queue.poll();

            int arr_size = list.get(now).size();

            for (int y = 0; y < arr_size; y++) {

                int base = list.get(now).get(y);

                in[base]--;

                dp[base] = Math.max(dp[base], time[base] + dp[now]);

                if (in[base] == 0) {
                    queue.add(base);
                }
            }

        }

        for (int x = 1; x <= building_num; x++) {
            bw.write(String.valueOf(dp[x]) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();




    }
}