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

20 Jul 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

위상 정렬을 이용하는 문제이다.

건물을 지을 때 먼저 지어야 할 건물이 정해져 있다.

즉, 먼저 지어야할 건물의 개수가 0이되면 지을 수 있는 것이다.

인접리스트로 건물을 지은 다음에 지을 수 있는 건물을 저장해놓는다.

in_degree 배열에 먼저 지어야 할 건물의 개수를 저장한다.

in_degree 배열이 0인 것부터 먼저 queue에 넣고 탐색하여 인접리스트에서 다음 건물의 in_degree값을 하나 빼준다.

in_degree 값이 0이되면 queue에 넣는다.

---

메모리: 21612KB

시간: 260ms

언어: Java 11

코드

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));
        int N = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 1; i <= N + 1; i++) {
            list.add(new ArrayList<>());
        }

        int[] time = new int[N + 1];
        int[] in_degree = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            while (true) {
                int from = Integer.parseInt(st.nextToken());
                if (from == -1) {
                    break;
                }
                list.get(from).add(i);
                in_degree[i]++;
            }
        }

        int[] answer = new int[N + 1];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < N + 1; i++) {
            if (in_degree[i] == 0) {
                queue.add(i);
                answer[i] = time[i];
            }
        }

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

            for (int next : list.get(node)) {
                answer[next] = Math.max(answer[next], answer[node] + time[next]);

                if (--in_degree[next] == 0) {
                    queue.add(next);
                }
            }
        }

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

        System.out.println(sb);
    }

}