[알고리즘] 백준1005_ACM Craft

백준 1005 ACM Craft

• 특정 출발지에서 도착지까지 가는 비용의 최대값
  • 특정 건물을 건설하기위해서는 그 전 건물들 건설 => 더 오래걸리는 시간으로 갱신
• 출발지는 여러 개 일 수도 있지만 도착지는 하나니까 도착지에서 출발하는 걸로. 안그럼 출발지 따로 저장해서 체크해야됨.
  • parents 배열에 그 전 지어야되는 건물_출발지 를 도착지 인덱스의 값으로 저장.
• dfs 로 갱신

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

public class Main {

    static int[] buildTime;                 // 각 건물 건설 시간
    static int[] dp;                        // 해당 건물 완성까지 걸리는 총 시간
    static ArrayList<Integer>[] parents;    // 역방향 그래프: parents[to] = to를 짓기 전에 필요한 건물들

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

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 건물 개수
            int K = Integer.parseInt(st.nextToken()); // 간선 개수

            buildTime = new int[N + 1];
            dp = new int[N + 1];
            parents = new ArrayList[N + 1];

            for (int i = 1; i <= N; i++) {
                parents[i] = new ArrayList<>();
                dp[i] = -1; 
            }

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

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                // 도착지에 출발지 저장
                parents[to].add(from);
            }

            int target = Integer.parseInt(br.readLine());

			// 도착지에서 출발. 
            sb.append(dfs(target)).append('\n');
        }

        System.out.print(sb);
    }

    static int dfs(int cur) {
    	// 계산 되어있으면 그대로
        if (dp[cur] != -1) return dp[cur];

        // 선행 건물이 없으면 자기 건설 시간만 필요
        if (parents[cur].isEmpty()) {
            dp[cur] = buildTime[cur];
            return dp[cur];
        }

		// 선행 건물 있으면 dfs 로 최대값 계산
        int maxPrev = 0;

        for (int prev : parents[cur]) {
            maxPrev = Math.max(maxPrev, dfs(prev));
        }

        dp[cur] = maxPrev + buildTime[cur];
        return dp[cur];
    }
}