[BOJ] 백준 1005 - ACM Craft 풀이

1. 문제

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

1005번: ACM Craft

2. 풀이

• 문제에서 핵심으로 생각한 부분은 "특정 건물을 짓고 다음 건물을 지을 수 있다" 부분이다. 이는 위상정렬의 "특정 과목을 수강한 후에 다른 과목을 수강할 수 있다"와 같다고 볼 수 있다.
• 기본적인 위상정렬과 같은 로직으로 돌아가지만 조금 다른 부분이 있다. 바로 건물을 짓는 시간에 대한 부분이다.
• 문제의 그림에도 나와 있는 예제 입력 1번을 보면, 1번 건물과 연결된 2번, 3번 건물을 동시에 짓기 시작하여도 4번을 짓기 위해서는 2번과 3번이 완성되어야 한다.
• 이를 다른 말로 하면 "현재 건물을 짓기 위해 걸리는 시간 = Max ("연결된 노드의 건물을 짓는데 걸리는 시간" + "현재 건물을 짓기 위해 걸리는 시간 " vs "현재 건물을 짓기 위해 걸리는 시간 ""이 된다.
  
  
• 이해를 돕기 위해 예제 입력 1번의 2번째 테스트 케이스를 보자 
  • 2번째 테스트 케이스는 "7"번 건물을 완성하면 게임을 끝낼 수 있다.
  • 우선 진입 차수가 0인 노드 (1번 건물)를 큐에 넣고 건설 시간을 입력하고 while문을 시작한다.
  • 1번 노드와 연결된 노드는 2번과 3번이므로 Max(2를 짓는 시간, 2를 짓는 시간 + 1을 짓는 시간), Max(2를 짓는 시간, 2를 짓는 시간 + 1을 짓는 시간)을 구하여 dp배열에 갱신한다.
  • 만약 처리 중인 노드의 진입 차수를 -1 했을 때 0이라면 큐에 넣는다.
  • 이를 반복하다가 poll을 했을 때 마지막 노드를 만난다면, 현재 result 값과 dp[poll] 배열의 값 중 큰 값으로 갱신한다.

3. 소스코드

package TopologicalSort;

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;


public class ACMCraft {
    static int N, K, W; // N : 건물 개수, K : 규칙 개수, W : 이기기 위해 지어야 하는 건물
    static Map<Integer, Integer> buildingMap; // 건물을 짓기 위한 비용이 저장된 맵
    static List<Integer>[] inList; // 인접리스트
    static int[] inDegree; // 진입 차수 배열
    static int result = 0; // 결과

    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 T = Integer.parseInt(br.readLine()); // 테스트케이스 수
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());

            // 비용을 맵에 저장
            buildingMap = new HashMap<>();
            for (int i = 1; i <= N; i++) {
                buildingMap.put(i, Integer.parseInt(st.nextToken()));
            }

            // 인접 리스트 초기화
            inList = new ArrayList[N + 1];
            for (int i = 1; i <= N; i++) {
                inList[i] = new ArrayList<>();
            }

            // 진입 차수 배열 초기화
            inDegree = new int[N + 1];

            // 인접 리스트 구성
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());

                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                inList[from].add(to);
                inDegree[to]++;
            }

            // 최종적으로 지어야 하는 건물 입력
            W = Integer.parseInt(br.readLine());

            // 위상정렬 함수 실행
            AcmTopologicalSort();

            // 결과를 버퍼에 출력
            bw.write(result + "\n");
            result = 0;
        }

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

    // 위상 정렬 함수
    private static void AcmTopologicalSort() {
        Queue<Integer> q = new ArrayDeque<>();
        int[] dp = new int[N + 1];

        // 진입 차수가 0인 노드를 모두 q에 offer
        // 이 떄 건물을 짓는 시간을 임시 배열에 대입
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
                dp[i] = buildingMap.get(i);
            }
        }

        while (!q.isEmpty()) {
            int poll = q.poll();

            // 꺼낸 노드가 최종적으로 필요한 건물이라면 건물을 짓는데 걸린 시간을 result에 대입
            if (poll == W) {
                result = Integer.max(result, tempTimeArr[poll]);
            }

            for (int i = 0; i < inList[poll].size(); i++) {
                int next = inList[poll].get(i);

                if (inList[poll].size() != 0) {
                    // 현재 노드(건물)를 건설하는 데 걸리는 시간 vs 이전 노드를 건설하는데 걸리는 시간 + 현재 노드(건물)를 건설하는 데 걸리는 시간
                    dp[next] = Math.max(dp[next], dp[poll] + buildingMap.get(next));
                }

                // 다음 노드의 진입 차수가 0이라면 큐에 넣는다.
                if (--inDegree[next] == 0) {
                    q.add(next);
                }
            }

        }
    }
}

4. 점수

75 / 100