[백준] 게임 개발 - Gold 3

[jusung-c]

문제 링크

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

문제 조건

• 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다.
• 각 건물마다 선행 건설이 필요한 건물 리스트와 건물을 짓는데 걸리는 시간이 주어진다.
• 각 건물을 짓는데 걸리는 시간은 10만보다 작거나 같은 수이다.

---

아이디어

먼저 정답의 최대치를 생각해보면 500개의 건물이 하나씩 나열된 순서이고, 각 10만의 시간이 걸린다면 총 5천만으로 int 자료형 안에서 가능하다.

1. 각 건물의 순서를 그래프로 나타낸다.
2. 가정 먼저 지을 수 있는 건물들부터 시작해서 위상 정렬을 시작한다.
3. 위상정렬을 하면서 각 건물을 짓는데 걸리는 최소 시간을 업데이트한다.
4. 이 때의 최소시간은 선행으로 지어져야 하는 건물들의 최대 시간에 현재 건물을 짓는데 걸리는 시간을 더해주면 된다.

---

시간 복잡도

간단한 위상정렬 문제로 O(V+E)의 시간이 걸리며 최대로 5천만이라 시간 안 풀이가 가능하다.

---

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    static StringTokenizer st;
    static int N;
    static int[] indeg, time, delay;
    static ArrayList<Integer>[] adj;

    public static void init() throws IOException {
        N = Integer.parseInt(br.readLine());

        indeg = new int[N + 1];
        time = new int[N + 1];
        delay = new int[N + 1];

        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) adj[i] = new ArrayList<>();

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

            while (true) {
                int num = Integer.parseInt(st.nextToken());
                if (num == -1) break;

                adj[num].add(i);
                indeg[i]++;
            }
        }

    }

    private static void pro() throws IOException {
        tpSort();

        for (int i = 1; i <= N; i++) {
            bw.write(time[i] + " ");
            bw.newLine();
        }
    }

    private static void tpSort() throws IOException {
        Queue<Integer> que = new LinkedList<>();

        for (int i = 1; i <= N; i++) {
            if (indeg[i] == 0) {
                que.add(i);
                time[i] += delay[i];
            }
        }

        while (!que.isEmpty()) {
            int x = que.poll();

            for (int y : adj[x]) {
                indeg[y]--;

                time[y] = Math.max(time[y], time[x] + delay[y]);
                if (indeg[y] == 0) que.add(y);
            }
        }

    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}