[BOJ/Java] 1005. ACM Craft

[BOJ/Java] 1005. ACM Craft

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

---

문제 해석

ACM Craft는 건물을 짓는 순서와 각 건물을 짓는 데 걸리는 시간이 주어졌을 때, 특정 건물을 완성하는 데 걸리는 최소 시간을 구하는 문제이다. 각 건물은 다른 건물이 먼저 지어져야만 지을 수 있으며, 이러한 의존 관계가 주어진다.

풀이 과정

1. 그래프 구성: 건물과 의존 관계를 그래프로 표현한다. 각 건물은 노드이며, 의존 관계는 방향성 간선이다.
2. 위상 정렬: 건물을 짓는 순서를 결정하기 위해 위상 정렬을 수행한다. 이때, 각 노드의 진입 차수(In-degree)를 관리한다.
3. 시간 계산: 각 건물을 짓는 데 걸리는 시간을 누적한다. 이때, 의존 관계에 있는 건물들이 모두 완성된 후에야 현재 건물을 지을 수 있으므로, 의존 건물들 중 가장 늦게 완성되는 시간을 기준으로 현재 건물의 완성 시간을 계산한다.
4. 결과 출력: 목표 건물의 완성 시간을 출력한다.

코드

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

public class Main {
    static int N, K, W;
    static int[] time, result, inDegree;
    static List<List> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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()); // 의존 관계의 수

            time = new int[N + 1]; // 각 건물을 짓는 데 걸리는 시간
            result = new int[N + 1]; // 각 건물을 완성하는 데 걸리는 총 시간
            inDegree = new int[N + 1]; // 각 건물의 진입 차수
            graph = new ArrayList<>(); // 의존 관계 그래프

            for (int i = 0; i <= N; i++) {
                graph.add(new ArrayList<>());
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                time[i] = Integer.parseInt(st.nextToken()); // 건물 짓는 시간 입력
            }

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());
                graph.get(X).add(Y); // X -> Y 의존 관계 추가
                inDegree[Y]++; // Y의 진입 차수 증가
            }

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

            topologicalSort(); // 위상 정렬 수행
            System.out.println(result[W]); // 목표 건물 완성 시간 출력
        }
    }

    static void topologicalSort() {
        Queue queue = new LinkedList<>();

        // 진입 차수가 0인 건물들을 큐에 추가한다.
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
                result[i] = time[i]; // 초기 건물은 자기 자신의 시간만 필요하다.
            }
        }

        while (!queue.isEmpty()) {
            int current = queue.poll(); // 현재 건물

            // 현재 건물과 연결된 다음 건물들을 확인한다.
            for (int next : graph.get(current)) {
                result[next] = Math.max(result[next], result[current] + time[next]); // 더 오래 걸리는 시간으로 갱신한다.
                inDegree[next]--; // 진입 차수 감소

                // 진입 차수가 0이 되면 큐에 추가한다.
                if (inDegree[next] == 0) {
                    queue.add(next);
                }
            }
        }
    }
}

시간 복잡도 분석

시간 복잡도는 O(N + K)이다. 위상 정렬을 수행하면서 모든 건물과 의존 관계를 한 번씩 처리하기 때문이다. 이는 문제의 제약 조건 내에서 효율적으로 동작한다.

느낀점

이 문제는 위상 정렬과 동적 프로그래밍을 결합한 전형적인 문제이다. 건물 간의 의존 관계를 그래프로 표현하고, 위상 정렬을 통해 건물을 짓는 순서를 결정한 후, 각 건물의 완성 시간을 누적하는 방식으로 문제를 해결할 수 있다. 처음에는 그래프를 어떻게 구성해야 할지 고민이 많았지만, 위상 정렬을 적용하니 문제가 명확히 풀렸다. 특히, 진입 차수를 관리하는 부분과 시간을 누적하는 부분이 핵심이었다. 이러한 유형의 문제는 실무에서도 작업 스케줄링이나 프로젝트 관리에 활용될 수 있을 것 같다.