[BOJ] 1005 ACM Craft

www.acmicpc.net/problem/1005

1005번: ACM Craft

어렵게 생각했는데.. 위상정렬 최대 값으로 해결함.  DP

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class boj_1005 {
    static int N, K, W;
    static int time[]; //i번째 빌딩을 짓는데 걸리는 시간
    static int dp[]; //i번째 빌딩을 짓는데 걸리는 총 시간, dp에 이전에 구한 값들을 저장 후 활용
    static boolean order[][];		//Y번째 선행 조건 X가 있으면 order[Y][X] = true

    static int DFS(int curr) { //curr가 진입차수가 아니면 curr까지 오기까지의 시간 중 가장 큰 시간 을 return한다.
        if(dp[curr]!=-1) {
            return dp[curr];
        }
        int ans = 0;
        for (int i = 1; i <= N ; i++) { //curr로 오기 위해 거쳐야할 곳들의 값을 미리 거쳐옴
            if(!order[curr][i]) continue;

            int tmp = DFS(i);
            if(tmp > ans) ans = tmp;
        }

        dp[curr] = ans + time[curr]; //현재 건물을 짓는데 걸리는 시간 + 현재까지 오기위해 걸린 시간
        return dp[curr];
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/boj1005_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

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

            time = new int[1001];
            dp = new int[1001];
            order = new boolean[1001][1001];

            Arrays.fill(dp, -1);

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

            int x, y;
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                x = Integer.parseInt(st.nextToken());
                y = Integer.parseInt(st.nextToken());
                order[y][x] = true;
            }

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

            System.out.println(DFS(W));
        }
    }
}