[BOJ] 1005. ACM Craft (🥇, DP/위상 정렬)

🔗

풀이

1 -> 2, 3 -> 4 와 5 -> 4 2가지 경로가 존재할 수 있다.

이때 매 노드마다 걸리는 시간들을 갱신해야 한다. 2, 3의 경우 1이라는 같은 출발지를 갖고 있기 때문에 30과 40의 시간이 최소로 걸리게 된다.

이제 4는 2, 3, 5 중 하나에서 도달할 수 있게 되는데, 이때 걸리는 시간의 최소값을 구하라고 하지만 실제로는 2, 3, 5가 모두 건설되어야 4가 건설될 수 있으므로 결국 2, 3, 5가 모두 건설될 수 있는 시간 즉 2, 3, 5 중 건설 시간의 최대값을 구해야 한다. 그 최대값에 4에 건설될 시간을 더하면 된다.

결국 목적 노드에 도달할 수 있는 선행 노드들 가운데 최대값을 구하고 그 값과 목적 노드의 건설 시간을 더해서 구할 수 있다.

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

public class Main {
    static BufferedReader br;
    static int solution() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] builtTime = new int[N+1];
        int[] connectCount = new int[N+1];
        List<List<Integer>> builtOrder = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            builtOrder.add(new ArrayList<>());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            builtTime[i] = Integer.parseInt(st.nextToken());
        }
        
        int X;
        int Y;
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            X = Integer.parseInt(st.nextToken());
            Y = Integer.parseInt(st.nextToken());
            connectCount[Y]++;
            builtOrder.get(X).add(Y);
        }

        int W = Integer.parseInt(br.readLine());
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (connectCount[i] == 0) {
                queue.add(i);
            }
        }

        int[] answer = Arrays.copyOf(builtTime, N+1);
        while (!queue.isEmpty()) {
            Queue<Integer> nextQueue = new LinkedList<>();
            while (!queue.isEmpty()) {
                int w = queue.poll();
                int timeW = answer[w];

                for (int nextW : builtOrder.get(w)) {
                    connectCount[nextW]--;
                    answer[nextW] = Math.max(answer[nextW], builtTime[nextW] + timeW);
                    if (connectCount[nextW] == 0) {
                        nextQueue.add(nextW);
                    }
                }
            }
            queue = nextQueue;
        }
        return answer[W];
    }
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            sb.append(solution() + "\n");
        }
        sb.replace(sb.length()-1, sb.length(), "");
        System.out.println(sb);
    }
}