[BOJ] 1005. ACM Craft

문제 원본 : https://www.acmicpc.net/problem/1005

1005번: ACM Craft

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n, k, x, y, w, curr;
        int[] d, c, ans;
        ArrayList<Integer>[] adj;
        Queue<Integer> queue;
        StringBuilder builder = new StringBuilder();

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            adj = new ArrayList[n + 1];
            d = new int[n + 1];
            c = new int[n + 1];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; ++i) {
                d[i] = Integer.parseInt(st.nextToken());
                adj[i] = new ArrayList<>();
            }

            for (int i = 0; i < k; ++i) {
                st = new StringTokenizer(br.readLine());
                x = Integer.parseInt(st.nextToken());
                y = Integer.parseInt(st.nextToken());
                adj[x].add(y);
                ++c[y];
            }

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

            queue = new ArrayDeque<>();
            ans = new int[n + 1];
            for (int i = 1; i <= n; ++i) {
                if (c[i] == 0) {
                    queue.add(i);
                    ans[i] = d[i];
                }
            }

            while (!queue.isEmpty()) {
                curr = queue.poll();

                if (curr == w) {
                    break;
                }

                for (int i : adj[curr]) {
                    --c[i];

                    if (c[i] == 0) {
                        queue.add(i);
                    }

                    ans[i] = Math.max(ans[i], ans[curr] + d[i]);
                }
            }

            builder.append(ans[w]).append("\n");
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }
}

• 위상 정렬 문제
• 타깃 건물이 지어지기 전 단계에서는 여러 건물이 동시에 지어질 수 있기 때문에
• 그중에서 제일 오래 걸리는 건물의 시간을 더해서 배열에 담아둔다.