[백준 1005] ACM Craft - JAVA

BOJ Link

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

 

 

풀이 과정

위상 정렬 + DP 문제이다.

스타크래프트 처럼 건물들 사이에 선행 건물이 존재할 때, 건물 G를 짓기 위한 총 비용을 구하는 문제이다. (동시에 지을 수 있다.)

 

선행 건물이 존재한다. 건설순서는 모든 건물이 건설 가능하도록 주어진다.

 

라는 조건은 이 조건은 방향그래프이며, 사이클이 없다는 것을 보장한다.

(A->B, B->A 형태의 사이클이라면, 건물이 건설 불가능하게 주어진 것이다.)

이로 인해 위상 정렬을 수행할 수 있다.

 

건물 A를 짓는데 필요한 총 비용은 DP로 구현한다.

단순히 생각하면, A의 비용 = 선행 건물을 짓는 최소 비용 + A 건물의 비용 이다.

 

A를 짓는데 B와 C가 필요하다 가정하면,

dp[a] = Math.max(cost[a]+dp[b], dp[a]);

dp[a] = Math.max(cost[a]+dp[c], dp[a]);

를 수행한다.

 

주의할 점은 cost[b]가 아닌 dp[b]로 비교해야, B를 짓는데 필요한 선행 건물들까지 고려할 수 있다.

또한, 선행 건물을 짓는 최소 비용 임에도 max를 써야한다. B=20, C=30일 때, B가 값이 더 작지만,

C또한 지어야 A를 지을 수 있으므로 최소한 30은 필요하다.

 

위상 정렬을 수행하며,

dp로 건물 i를 짓는데 필요한 dp[i]를 갱신한다.

진입 차수가 0인 건물은 지을 수 있다는 것(선행 건물들을 모두 지었다는 것)이므로 큐에 넣는다.

탐색이 끝나면 목표 건물 g의 건설 비용인 dp[g]를 출력한다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int TC = Integer.parseInt(br.readLine());

        for (int t = 0; t < TC; t++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            int[] cost = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            // 총 비용 : 현재 건물 비용 + 선행 건물 비용 최대 값
            int[] dp = Arrays.stream(cost).toArray();
            int[] indegree = new int[N];

            // List 사용 => O(V+E), Array 사용 => O(V^2)
            int[][] adj = new int[N][N];

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken()) - 1;
                int to = Integer.parseInt(st.nextToken()) - 1;

                // 방향 그래프임
                adj[from][to] = 1;
                // 진입 차수
                indegree[to]++;
            }

            int G = Integer.parseInt(br.readLine()) - 1;
            int total = 0;

            Queue<Integer> q = new ArrayDeque<>();

            for (int i = 0; i < N; i++) {
                if (indegree[i] == 0) {
                    q.offer(i);
                }
            }
            
            while (!q.isEmpty()) {
                int now = q.poll();

                if (now == G) break;

                for (int i = 0; i < N; i++) {
                    if (adj[now][i] == 1) {
                        indegree[i]--;
                        dp[i] = Math.max(dp[now] + cost[i], dp[i]);

                        if (indegree[i] == 0) {
                            q.offer(i);
                        }
                    }
                }
            }

            System.out.println(dp[G]);
        }
    }
}