• 장난감 조립 : ACM Craft와 매우 유사한 문제이다. 차이점이라면 모든 Node에 대해 값을 구해야 하므로, 부품을 만드는 데 걸린 시간을 저장한 배열 값을 모두 출력해야 한다는 정도이다.

• 게임 개발 : 장난감 조립과 매우 유사한 문제이다.

---

문제 이해

건물 짓는 순서가 정해 주어질 것이다.
또한, 이전에 꼭 지어져야 할 건물이 지어지지 않는다면 해당 건물은 짓지 못한다.
예를 들어, B,C를 지어야만 A를 지을 수 있는 경우, B만 지어졌을 때 A를 지울 수는 없다.

이 경우 특정 건물을 가장 빨리 지을 때까지 걸린 최소 시간을 알아보는 문제이다.

---

문제 풀이

A ⇒ B : B를 짓기 위해서는 A를 꼭 지어야한다.
이 경우 절대 A ⇒ B ⇒ A 같은 경우는 벌어지지 않을 것이다. 왜냐면 이 경우, A와 B 건물을 영원히 짓지 못할 것이기 때문이다.

사이클이 존재하지 않으며, 방향(화살표)가 존재하는 그래프, 즉 DAG이다.
따라서 위상 정렬을 통해 문제를 해결하였다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N,K;
	static ArrayList<Integer>[] edges;
	static int[] time; 
    // 각 건물 하나를 세울 때 걸리는 시간(사전에 세워야 할 건물 짓는 시간 제외)
	static int[] ans;
    // 특정 건물을 짓는데 걸리는 총 시간
	static int[] input;

	static void sort(int end) {
		Queue<Integer> queue = new LinkedList<>();
		for(int i =1;i<N+1;i++) {
			if(input[i]==0) queue.add(i);
		}
		
		while(!queue.isEmpty()) {
			int tmp = queue.poll();
			
			if(tmp==end) { // 원하는 건물을 짓는 순간
				sb.append(ans[tmp]).append("\n");
				return;
			}
			
			for(int s:edges[tmp]) {
				ans[s] = Math.max(ans[s], time[s]+ans[tmp]);
                // ans[s] : 원래 저장되어 있던 값
                // time[s] + ans[tmp] : s를 짓기 위해서는 tmp를 미리 
                //                      지어 놔야한다.
                //                      따라서, s를 짓는 시간은 
                //                      최소 time[s] + ans[tmp] 값을 가진다
                // 두 값 중 큰 값만큼 s를 짓는데 소요될 것이다.              

				input[s]--; 
                // tmp Node를 삭제시킬 것이므로 tmp와 연결된
                // 모든 Node들에 대해 input값을 1 빼줌
				if(input[s]==0) queue.add(s);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		int T = sc.nextInt();
		
		for(int t=0;t<T;t++) {
			
			N = sc.nextInt();
			K = sc.nextInt();
			
			edges = new ArrayList[N+1];
			time = new int[N+1];
			ans = new int[N+1];
			input = new int[N+1];
			
			for(int i =1;i<N+1;i++) {
				edges[i] = new ArrayList<>();
				time[i] = sc.nextInt();
				ans[i] = time[i];
			}
			
			for(int i =0;i<K;i++) {
				int tmp1 = sc.nextInt();
				int tmp2 = sc.nextInt();
				
				input[tmp2]++;          
				edges[tmp1].add(tmp2);
                // tmp2를 짓기 위해서는 tmp1을 미리 지어놔야 함
                // 즉, 화살표가 tmp1 -> tmp2이므로
                // input[tmp2]를 1 증가시킴 & list[tmp1]에 tmp2추가
			}
			
			sort(sc.nextInt());
		}
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과