[BOJ/JAVA] 1005번: ACM Craft

1005번: ACM Craft

1005번: ACM Craft

키워드

모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다.

매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.

특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램

---

구현

i 건물을 짓는데 필요한 선행 건물의 인접리스트를 구현한다.

위 그림에서

4번 건물을 짓기 위해서 2, 3의 건물 인덱스를 삽입한다.

2, 3건물도 마찬가지로 1번 건물 인덱스를 삽입한다.

문제에서는 최소시간을 알아내라고 했지만, 4기준으로 2, 3건물 둘 중 하나가 지어지기 위해서는 더 늦게 지어지는 건물을 우선적으로 선택해야 한다. 따라서 최댓값을 반환하면 최소시간이 나오게 된다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class java_1005 {
    static int T;
    static int N;
    static int K;
    static int W;

    static int buildingList[];

    static List<List<Integer>> tree;

    static int cache[];

    static int dp(int index) {
        if (tree.get(index).size() == 0) {
            return buildingList[index];
        }

        if (cache[index] != -1) {
            return cache[index];
        }

        cache[index] = 0;

        for (int i = 0; i < tree.get(index).size(); i++) {
            int there = tree.get(index).get(i);
            cache[index] = Math.max(cache[index], dp(there) + buildingList[index]);
        }

        return cache[index];
    }

    static int solve() {
        int result = 0;

        cache = new int[N];
        Arrays.fill(cache, -1);

        result = dp(W);

        return result;
    }

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

        T = Integer.parseInt(br.readLine());
        for (int testCase = 0; testCase < T; testCase++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            buildingList = new int[N];
            tree = new ArrayList<>();

            // 건물 건설 시간
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                tree.add(new ArrayList<>());
                buildingList[i] = Integer.parseInt(st.nextToken());
            }

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int to = Integer.parseInt(st.nextToken()) - 1;
                int from = Integer.parseInt(st.nextToken()) - 1;
                tree.get(from).add(to);
            }

            W = Integer.parseInt(br.readLine()) - 1;

            int result = solve();

            System.out.println(result);
        }

        br.close();
    }
}

---