백준 1516 게임 개발 Java [위상정렬, DP]

https://www.acmicpc.net/problem/1516

1516번: 게임 개발

 

위상정렬을 사용하여 먼저 지어야하는 건물 갯수만큼 가중치를 주고,

건물이 완성될 때마다 그 다음 지을 수 있는 건물의 시간 값을 최대값을 비교하여 넣어주고,

가중치가 0이 되면 건물 완성 큐에 넣는다

 

예제를 예시로 하면 가중치는 [0, 0, 1, 1, 2, 1]이 된다 (0번 인덱스는 사용안함)

가중치가 0인 값을 큐에 넣으면 1번만 큐에 들어간다

1 다음에 지을 수 있는 건물은 2, 3, 4이고

2, 3, 4의 건설 완료 시간에 10 + @(해당 인덱스 건설 시간)로 최대값을 넣는다 (20, 14, 14)

2, 3은 가중치가 0이고 4는 1이므로 2, 3만 큐에 넣는다

2는 다음 건물이 없으니 넘어가고 3은 다음 건물이 4, 5이다

4, 5의 건설 완료 시간에 14 + @로 최대값을 넣는다 (18, 17)

이전에 4에 저장된 값이 14인데 18보다 작으므로 18로 바뀐다

둘다 가중치가 0이니 큐에 넣지만 다음 건물이 없으므로 반복문이 종료된다

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        int[] times = new int[N + 1];
        int[] weights = new int[N + 1];
        ArrayList<Integer>[] childs = new ArrayList[N + 1];
        for (int n = 1; n <= N; n++) childs[n] = new ArrayList<>();
        for (int n = 1; n <= N; n++) {
            int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            times[n] = arr[0];
            weights[n] += arr.length - 2;
            for (int i = 1; i < arr.length - 1; i++) {
                childs[arr[i]].add(n);
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int n = 1; n <= N; n++) {
            if (weights[n] == 0) {
                queue.add(n);
                dp[n] = times[n];
            }
        }
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int child : childs[now]) {
                dp[child] = Math.max(dp[child], dp[now] + times[child]);
                weights[child]--;
                if (weights[child] == 0) queue.add(child);
            }
        }
        for (int n = 1; n <= N; n++) sb.append(dp[n]).append("\n");
        System.out.println(sb);
    }
}