[백준] 1005번 - ACM Craft (Gold 3)

문제 링크

백준 1005번 - ACM Craft (Gold 3)

문제 설명

주어진 건물 건설 규칙을 만족하면서 특정 건물을 짓는데 걸리는 최소 시간을 출력한다. 건물 건설 규칙은 두 가지로 이루어져 있다.

1. 각 건물 당 건설에 걸리는 시간
   • 건물 1번부터 N번까지 순서대로 짓는데 걸리는 시간이 주어진다.
2. 건물 건설 순서
   • 건물을 짓기 전에 반드시 먼저 지어져야하는 건물들의 번호가 주어진다.

정답 코드 및 설명

건물 i를 짓는데 걸리는 시간을 $A_i$, 건물 건설 규칙을 만족하면서 짓는데 걸리는 최소 시간을 $T_i$라고 하자.
건물 W를 짓기 전에 지어야하는 건물들이 $V_1, \cdots, V_k$라면 $T_W = \textrm{max}(A_{V_1}, \cdots A_{V_k}) + A_W$이다.
건설 순서는 항상 모든 건물이 건설 가능하도록 주어진다고 했으므로, 사이클이 도는 경우는 없고 언젠가는 이 과정이 끝날 것이다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1005 {
    int n, k, w;
    int[] time;
    int[] minTime;
    ArrayList<Integer>[] parents;

    void input(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        time = new int[n];
        parents = new ArrayList[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            time[i] = Integer.parseInt(st.nextToken());
            parents[i] = new ArrayList<>();
        }
        int before, after;
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            before = Integer.parseInt(st.nextToken()) - 1;
            after = Integer.parseInt(st.nextToken()) - 1;
            parents[after].add(before);
        }
        w = Integer.parseInt(br.readLine()) - 1;
    }

    int time(int w) {
        if (minTime[w] != -1) {
            return minTime[w];
        }
        int maxTime = 0;
        int curr;
        for (int i : parents[w]) {
            curr = time(i);
            if (curr > maxTime) maxTime = curr;
        }
        minTime[w] = maxTime + time[w];
        return minTime[w];
    }

    void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            input(br);
            minTime = new int[n];
            Arrays.fill(minTime, -1);
            bw.write(time(w) + "\n");
        }
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        new BOJ1005().solution();
    }
}