[백준(Baekjoon)][자바(java)] 1005 : ACM Craft / 위상 정렬

 

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

1005번: ACM Craft

 

문제 풀이

 

*  DFS + DP

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
	static List<List<Integer>> edge_in;
	static int time[];
	static long dp[];
	
	public static long dfs(int u) {
		if (dp[u] != -1) return dp[u];
		long time_max = 0;
		for (int v : edge_in.get(u))
			time_max = Math.max(time_max, dfs(v));
		time_max += time[u];
		return dp[u] = time_max;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int t = Integer.parseInt(br.readLine()), n, k, w, u, v, i;
		StringBuilder sb = new StringBuilder();
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			time = new int[n];
			st = new StringTokenizer(br.readLine());
			for (i = 0; i < n; ++i)
				time[i] = Integer.parseInt(st.nextToken());
			edge_in = new ArrayList<>();
			for (i = 0; i < n; ++i)
				edge_in.add(new ArrayList<>());
			for (i = 0; i < k; ++i) {
				st = new StringTokenizer(br.readLine());
				u = Integer.parseInt(st.nextToken()) - 1;
				v = Integer.parseInt(st.nextToken()) - 1;
				edge_in.get(v).add(u);
			}
			w = Integer.parseInt(br.readLine()) - 1;
			dp = new long[n];
			for (i = 0; i < n; ++i)
				dp[i] = -1;
			sb.append(dfs(w) + "\n");
		}
		br.close();
		System.out.println(sb.toString());
	}
}