[백준 1005번] ACM Craft

문제 링크: 1005번 제목

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

 

대표적인 위상정렬 문제로 보인다.

위상정렬에 대해서는 여기에 포스팅해두었다.

 

아래에서 accu는 해당 건물을 짓기 직전까지 필요한 최소 시간을 저장하고 있다.

그런데 무작정 최솟값만 갱신하면 되는 것이 아니다. 왜냐하면 '어떤 건물'을 짓기 위한 여러 선결 조건이 있을 때, 해당 조건들은 모두 만족되어야만 하기 때문에, 요구사항이 가장 거대한 건물이 완성되어야만 '어떤 건물'을 지을 수 있다. 그렇기에 최댓값을 갱신해준다.

 

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));
        int test = Integer.parseInt(br.readLine());
        while (test-- > 0) {
            // input begins
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(st.nextToken()); // number of buildings
            int k = Integer.parseInt(st.nextToken()); // number of rules
            int[] need = new int[n+1]; // time required to build (single demand)
            int[] accu = new int[n+1]; // time required to build (accumulated for precedents)
            int[] indegree = new int[n+1];
            List<Integer>[] graph = new ArrayList[n+1];
            for (int i = 1; i <= n; i++) {
                graph[i] = new ArrayList<>();
            }
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 1; i <= n; i++) {
                need[i] = Integer.parseInt(st.nextToken());
            }
            for (int i = 0; i < k; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                indegree[b]++;
                graph[a].add(b);
            }
            int target = Integer.parseInt(br.readLine());
            // input ends

            Queue<Integer> queue = new LinkedList<>();

            for (int i = 1; i <= n; i++) {
                if (indegree[i] == 0) {
                    accu[i] = 0;
                    queue.offer(i);
                }
            }

            for (int cnt = 0; cnt < n; cnt++) {
                int dept = queue.poll();
                for (int dest : graph[dept]) {
                    indegree[dest]--;
                    if (accu[dest] < accu[dept] + need[dept]) {
                        accu[dest] = accu[dept] + need[dept];
                    }
                    if (indegree[dest] == 0) {
                        queue.offer(dest);
                    }
                }
            }

            System.out.println(accu[target] + need[target]);
        }
    }
}