[BOJ] 1516 게임 개발 - JAVA

📚 Problem

1516 게임 개발

📝 Solution

• 건물을 짓는 것에 순서가 존재
• 여러개의 건물을 동시에 짓는 것이 가능

각 건물의 최소시간을 구하기 위해 위상정렬 과 DP 를 사용했습니다

• 현재의 건물을 짓기 위해 먼저 지어야 하는 건물을 짓는 시간에다가 현재 건물을 짓는 시간을 더하면 현재 건물을 짓는 시간이 나오게 됩니다
• 근데 여기서 먼저 지어야 하는 건물이 여러개일 경우, 각 건물을 동시에 짓는 것이 가능한데
  그러면 그 여러개의 건물들 중 건물을 짓는데 걸리는 시간의 최댓값이 먼저 지어야 하는 건물을 짓는 시간이 됩니다

다음 건물을 짓는 최소 시간 = max(다음 건물을 짓는 최소 시간, 현재 건물을 짓는 최소 시간 + 현재 건물을 짓는 시간)

위의 식으로 도출된 최소시간에 다음 건물을 짓는 시간을 더하게 된다면 건물을 짓는데 걸리는 최소시간을 얻을 수 있습니다

indegree : 해당하는 인덱스의 앞에 오는 수의 개수를 가진 배열
graph : 해당 인덱스에 해당하는 숫자의 뒤에 오는 숫자들의 리스트

• 조건을 입력받으며 indegree 배열과 graph 생성

            if (preBuildingNum == -1) {
                buildings.add(new Building(i, time));
                continue;
            }

            buildings.add(new Building(i, time));
            while (preBuildingNum != -1) {
                graph[preBuildingNum].add(i);
                indegree[i]++;
                preBuildingNum = scanner.nextInt();
            }

• indegree 의 값이 0이라는 뜻은, 앞에 와야하는 숫자가 1개도 없다는 뜻이므로 큐에 삽입

        for (int i = 1; i <= N; i++)
            if (indegree[i] == 0)
                queue.add(i);

• Queue에서 poll()을 하여 나온 숫자의 뒤에 오는 숫자들의 indegree를 하나씩 줄이면서,
  next 에 해당하는 건물을 짓는 최소한의 시간을 구합니다

        while(!queue.isEmpty()){
        int current = queue.poll();

        for(int i = 0; i < graph[current].size(); i++){
        int next = graph[current].get(i);
        indegree[next]--;
        minTime[next] = Math.max(minTime[next], minTime[current] + buildings.get(current).time);

        if(indegree[next] == 0)
        queue.add(next);
        }

💻 Code

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Building{
    int num;
    int time;

    public Building(int num, int time){
        this.num = num;
        this.time = time;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N;
        int[] minTime;
        int[] indegree;
        ArrayList<Integer>[] graph;
        ArrayList<Building> buildings = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        N = scanner.nextInt();
        minTime = new int[N + 1];
        indegree = new int[N + 1];
        graph = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++)
            graph[i] = new ArrayList<>();

        buildings.add(new Building(0,0)); // add 0 index building

        for (int i = 1; i <= N; i++) {
            int time = scanner.nextInt();
            int preBuildingNum = scanner.nextInt();

            if (preBuildingNum == -1) {
                buildings.add(new Building(i, time));
                continue;
            }

            buildings.add(new Building(i, time));
            while (preBuildingNum != -1) {
                graph[preBuildingNum].add(i);
                indegree[i]++;
                preBuildingNum = scanner.nextInt();
            }
        }

        for (int i = 1; i <= N; i++)
            if (indegree[i] == 0)
                queue.add(i);

        while(!queue.isEmpty()){
            int current = queue.poll();

            for(int i = 0; i < graph[current].size(); i++){
                int next = graph[current].get(i);
                indegree[next]--;
                minTime[next] = Math.max(minTime[next], minTime[current] + buildings.get(current).time);

                if(indegree[next] == 0)
                    queue.add(next);
            }
        }

        for (int i = 1; i <= N; i++)
            System.out.println(buildings.get(i).time + minTime[i]);

        scanner.close();
    }
}