BOJ_1005 : ACM Craft

👉 문제링크

1005번: ACM Craft

---

🔸 문제 분석 🔸

• 앞선 건물들이 모두 지어져야 해당 건물을 지을 수 있게 되는 건물 순서 규칙이 존재한다.
• 건물은 동시에 여러 개를 지을 수 있다.
• 목표 건물을 짓는데 드는 최소 시간을 출력한다.

🔸 문제 풀이 🔸

1. 건물이 지어지는 순서가 달라질 수 있는데 선행 작업이 존재하므로, 위상 정렬을 사용해서 풀이한다.
2. 동시에 건물을 지었다고 할 때, 가장 오래 걸리는 건설 시간이 최소값이다. 따라서 최대값을 갱신해서 저장하기 위해 DP를 사용한다.
   1. 점화식은 다음과 같다.  [현재 건물의 최대 건설 시간] = max([이전 건물의 최대 건설 시간 + 현재 건물 건설 시간], [현재 건물의 최대 건설 시간]) 
3. 위상 정렬 알고리즘의 동작 과정은 다음과 같다.
   1. 진입차수가 0인 모든 노드를 큐에 넣는다.
   2. 큐가 빌 때까지 다음의 과정을 반복한다.
      • 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
      • 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 건물 수
            int K = Integer.parseInt(st.nextToken()); // 건물 짓는 순서 개수

            int[] bt = new int[N + 1]; // 건물 짓는 시간
            ArrayList<Integer>[] adjList = new ArrayList[N + 1]; // 건물 짓는 순서
            int[] input = new int[N + 1]; // 선행 규칙 수
            int[] dp = new int[N + 1];

            // 건물 짓는 시간 저장
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                bt[j] = Integer.parseInt(st.nextToken());
                adjList[j] = new ArrayList<>();
            }

            // 건물 짓는 순서 저장 & 선행 규칙 카운트
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());
                adjList[X].add(Y);
                input[Y]++;
            }

            // 선행 규칙이 0개인 건물 부터 시작
            Queue<Integer> que = new ArrayDeque<>();
            for (int j = 1; j <= N; j++) {
                if (input[j] == 0) {
                    que.add(j);
                    dp[j] = bt[j];
                }
            }

            while (!que.isEmpty()) {
                int now = que.poll();

                for (int next : adjList[now]) { // 현재 건물과 연결된 건물의 선행 규칙 -1
                    input[next]--;
                    dp[next] = Math.max(dp[now] + bt[next], dp[next]); // 건물을 짓는데 걸리는 시간 최대값으로 갱신
                    if (input[next] == 0) { // 선행 규칙이 0개가 되면 큐에 넣어주기
                        que.add(next);
                    }
                }
            }
            sb.append(dp[Integer.parseInt(br.readLine())]).append('\n');
        }
        bw.write(sb.toString());
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 건물 수, 짓는 순서, 짓는 시간을 입력받고, 각 건물의 선행 규칙 수를 카운트한다.
• 선행규칙 0인 건물들 부터 큐에 넣고 위상 정렬과 DP를 적용한다.
  • 현재 건물과 연결 된 다음 건물의 진입 차수를 -1 한다.
  • 건물을 짓는데 걸리는 시간의 최대값을 dp에 갱신한다.
  • 진입 차수가 0이 되면 큐에 넣는다.
• dp 배열에서 최소시간을 구하고자 하는 건물의 인덱스를 넣어 답을 출력한다.

---

🔸 end 🔸

•  처음엔 그리디로 풀이하려고 했지만, 예제 2번의 3번째 케이스에서 실패했다. 선행 작업이 여러 가지가 겹쳐 있는 상태를 반영하지 못했다.
• 알고리즘이 생각나지 않아 풀이 포스팅을 참고해 풀이했다.
  • 위상 정렬과 DP를 사용하면 된다는 걸 알고 바로 쉽게 풀이할 수 있었다.
  • 위상 정렬은 생각보다 어렵지 않은데, 뒤늦게 배워서 괜히 어렵게 인식하고 있는 것 같다. 더 연습하도록 하자.