BOJ_1005_ACM Craft_java

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

1005번: ACM Craft

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

/**
 백준 1005번 ACM Craft
 골드 3
 */
public class BOJ_1005_ACM_Craft {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine()); // 테스트 케이스
        for (int tc = 1; tc<=T; tc++){
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 건물 수
            int K = Integer.parseInt(st.nextToken()); // 건물 건설 순서 규칙
            int[] inDegree = new int[N+1]; // 노드 진입 차수
            List<Integer>[] edges = new List[N+1]; // 간선 정보
            for (int i = 1; i<=N; i++){ // 간선 정보 초기화
                edges[i] = new ArrayList<>();
            }
            int[] dp = new int[N+1]; // 노드 도달 비용 dp 배열
            int[] D = new int[N+1]; // 건물 건설 시간
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i<=N; i++){
                D[i] = Integer.parseInt(st.nextToken());
            }

            for (int i = 0; i<K; i++){ // 건설 순서 규칙
                st = new StringTokenizer(br.readLine());
                int before = Integer.parseInt(st.nextToken());
                int after = Integer.parseInt(st.nextToken());
                edges[before].add(after);
                inDegree[after]++;
            }

            int W = Integer.parseInt(br.readLine()); // 목표 건물 번호

            // 위상정렬
            Queue<Integer> queue = new LinkedList<>();
            boolean flag = false; // 중간 종료용 flag
            for (int i = 1; i<=N; i++){
                if (inDegree[i] == 0){
                    queue.offer(i); // 시작 노드
                    dp[i] = D[i];
                    while (!queue.isEmpty()){
                        int node = queue.poll();
                        if (node == W){ // 목표 건물
                            sb.append(dp[node]).append("\n");
                            flag = true;
                            break;
                        }
                        inDegree[node] = -1;
                        for (int next : edges[node]){
                            inDegree[next]--;
                            dp[next] = Math.max(dp[next], dp[node] + D[next]); // 이전 건물 모두 건설이 완료되어야함 -> max
                            if (inDegree[next] == 0){
                                queue.offer(next);
                            }
                        }
                    }
                    if (flag) break;
                }
            }
        }

        System.out.println(sb.toString());
    }
}