- 특정 건물을 건설하기 위해서는 자신을 가리키는 건물이 모두 지어져야 한다. 즉, 정점에 진입 간선이 없어야 건설이 가능하므로 위상 정렬을 사용한다.
- 목표 건물까지 도달하는데 필요한 가중치의 합 중 가장 큰 값이 정답이 된다.
→ 이 시간보다 짦은 시간이 걸리는 경로는 해당 경로의 건물들이 모두 지어질 때까지 기다려야 목표 건물을 건설할 수 있기 때문이다.- 각 정점마다 해당 정점에 오는데 필요한 시간 합의 최댓값을 배열에 저장해둔다.
이렇게 생각을 정리하고 코드를 짜면 다음과 같습니다.
import java.io.*;
import java.util.*;
//백준 1005 ACM Craft
public class b1005 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int t = 0;t < T;t++) {
String str[] = br.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
ArrayList<Integer> graph[] = new ArrayList[N + 1]; // 위상 정렬을 위한 그래프
for(int i = 0; i <= N;i++) {
graph[i] = new ArrayList<>();
}
int inDegree[] = new int[N + 1];
str = br.readLine().split(" ");
int weight[] = new int[N + 1];
int dp[] = new int[1001]; // 정점까지의 필요한 시간 합의 최댓값 저장할 배열
for(int i = 0;i < str.length;i++) weight[i + 1] = Integer.parseInt(str[i]);
int a, b;
for(int i = 0;i < M;i++) {
str = br.readLine().split(" ");
a = Integer.parseInt(str[0]);
b = Integer.parseInt(str[1]);
// 간선을 추가하고 진입차수를 기록
graph[a].add(b);
inDegree[b]++;
}
int goal = Integer.parseInt(br.readLine());
Queue<Integer> q = new ArrayDeque<>();
//위상정렬을 하기 위해 진입차수가 0인 정점을 먼저 큐에 삽입
for(int i = 1;i <= N;i++) {
if(inDegree[i] == 0) {
q.add(i);
dp[i] = weight[i]; // 가장 처음 큐에 들어오는 정점은 최댓값이 자기 자신
}
}
while(!q.isEmpty()) {
int cur = q.poll();
if(cur == goal) break;
for(int i = 0;i < graph[cur].size();i++) {
int node = graph[cur].get(i);
dp[node] = Math.max(dp[node], dp[cur] + weight[node]); // node라는 정점까지의 최댓값 구하기
// 이 때, 진입차수가 0이 되지 않더라도 최댓값은 구해줘야 한다는 점에 유의
if(--inDegree[node] == 0) {
q.add(node);
}
}
}
System.out.println(dp[goal]);
}
}
}