[BOJ] 백준 1516 - 게임 개발 (Java)

1516 - 게임 개발

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

문제

게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 최소 시간 이용
어떤 건물을 짓기 위해 다른 건물을 먼저 지어야 할 수 있음
ex. 스타크래프트: 벙커 짓기 위해서는 배럭을 먼저 지어야 함
여러 개의 건물 동시에 지을 수 있음
자원 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않음

입력
첫째 줄: 건물의 종류 수 N (1 <= N <= 500)
다음 N개 줄: 각 건물을 짓는데 걸리는 시간, 건물을 짓기 위해 먼저 지어야 하는 건물들의 번호
(건물의 번호 1 ~ N, 각 줄은 -1로 끝남/ 건물을 짓는데 걸리는 시간 <= 100,000)
출력: N개의 각 건물이 완성되기까지 걸리는 최소 시간

---

풀이

• `graph[a]`: 건물 a를 짓고 난 뒤 지을 수 있는 건물 리스트
• `inDegree[i]`: 건물 i를 짓기 위한 선행 건물 수
• ex. 건물 i를 짓기 전 1과 3을 지어야 함
  • `graph[1].add(i)`, `graph[3].add(i)`
  • `inDegree[i] = 2`

• `time[i]`: 건물 i 자체의 건설 시간
• `result[i]`: 건물 i를 짓기까지 걸리는 총 시간

graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
    graph.add(new ArrayList<>());
}

inDegree = new int[N + 1];
time = new int[N + 1];
result = new int[N + 1];

 

• 진입 차수 0 = 선행 건물 X 건물 -> 자기 `time[i]`만큼 걸림
• 위상 정렬 + DP
  • `result[next]`: 현재 건물까지 걸리는 총 시간/ 두 값 중 더 큰 값
    • `result[next]`: 지금까지 계산된 `next`의 완성 시간
    • `result[cur] + time[next]`: `cur`를 끝낸 뒤 `next`를 짓는 경우의 시간
  • 진입 차수 0되면 큐에 넣고 반복 

Queue<Integer> q = new ArrayDeque<>();
for (int i = 1; i <= N; i++) {
    result[i] = time[i];
    // 진입 차수 0
    if (inDegree[i] == 0) q.offer(i);
}

while (!q.isEmpty()) {
    int cur = q.poll();

    for (int next : graph.get(cur)) {
        result[next] = Math.max(result[next], result[cur] + time[next]);
        inDegree[next]--;

        if (inDegree[next] == 0) q.offer(next);
    }
}

---

코드

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

// 게임 개발
public class boj_1516 {
    static int N;
    static List<List<Integer>> graph;
    static int[] inDegree, time, result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        inDegree = new int[N + 1];
        time = new int[N + 1];
        result = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());

            while (true) {
                int pre = Integer.parseInt(st.nextToken());
                if (pre == -1) break;
                graph.get(pre).add(i);
                inDegree[i]++;
            }
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            result[i] = time[i];
            if (inDegree[i] == 0) q.offer(i);
        }

        while (!q.isEmpty()) {
            int cur = q.poll();

            for (int next : graph.get(cur)) {
                result[next] = Math.max(result[next], result[cur] + time[next]);
                inDegree[next]--;

                if (inDegree[next] == 0) q.offer(next);
            }
        }

        for (int i = 1; i <= N; i++) {
            sb.append(result[i]).append("\n");
        }

        System.out.println(sb);
    }
}