ACM Craft

백준 [1005] ACM Craft

풀이 1. 메모이제이션 + dfs 활용

건설하고자 하는 건물의 사전 건물들의 건설 시간을 탐색한다. 이미 확인된 건물의 시간은 탐색하지 않고 사전에 탐색한 시간을 활용한다.

참고 : 건물을 짓는 시간이 모두 0초 인 경우를 고려하여 건설 여부를 -1로 세팅한다. 0초로 세팅하는 경우 무한루프를 돌아 시간초과 발생

Alt text

소스코드 1.

import java.util.*;

public class Main {
    public static void main(String[] agrs) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        for (int tc = 0; tc < T; tc++) {
            int N = sc.nextInt(); // 건물의 갯수
            int K = sc.nextInt(); // 건설 규칙 갯수

            // 건물 별 건설 시간
            int[] D = new int[N];
            for (int i = 0; i < N; i++) {
                D[i] = sc.nextInt();
            }

            // 건물 순서 규칙 입력 (key : 건물 번호, value: 건물이 지어지기 위해 사전에 지어져야하는 건물들)
            Map<Integer, List<Integer>> roleMap = new HashMap<>();
            for (int xy = 0; xy < K; xy++) {
                int x = sc.nextInt() - 1;
                int y = sc.nextInt() - 1;

                roleMap.computeIfAbsent(y, key -> new ArrayList<>()).add(x);
            }

            int W = sc.nextInt() - 1; // 건설하고자 하는 건물 번호

            int[] buildTime = new int[N];
            Arrays.fill(buildTime, -1);

            int buildingTime = getBuildingTime(roleMap, D, buildTime, W);
            System.out.println(buildingTime);
        }
    }

    private static int getBuildingTime(Map<Integer, List<Integer>> roleMap, int[] D, int[] buildTime, int currentNo) {
        // 건물의 시작점에 도달한 경우
        if (!roleMap.containsKey(currentNo)) {
            buildTime[currentNo] = D[currentNo];
            return buildTime[currentNo];
        }

        // 건물이 이미 지어진 경우
        if (buildTime[currentNo] != -1) {
            return buildTime[currentNo];
        }

        List<Integer> beforeBuildings = roleMap.get(currentNo);
        int maxBeforeBuildTime = 0;

        for (int beforeNo : beforeBuildings) {
            // 아직 사전 건물의 시간을 모르는 경우
            if (buildTime[beforeNo] == -1) {
                buildTime[beforeNo] = getBuildingTime(roleMap, D, buildTime, beforeNo);
            }

            maxBeforeBuildTime = Math.max(maxBeforeBuildTime, buildTime[beforeNo]);
        }

        buildTime[currentNo] = maxBeforeBuildTime + D[currentNo];

        return buildTime[currentNo];
    }
}

풀이 2. 메모이제이션 + 위상정렬 활용

건설 시작점이 되는 건물을 찾아 위상정렬 알고리즘을 활용한다.

참고 : 위상정렬은 사이클이 발생하지 않을때만 사용 가능하다.
[queue 구현 성능 차이 참고] 첫번째 줄 : ArrayDeque 사용, 두번째 줄 : LinkedList 사용

소스코드 2.

import java.util.*;

public class Main {
    public static void main(String[] argd) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        for (int tc = 0; tc < T; tc++) {
            int N = sc.nextInt(); // 건물의 갯수
            int K = sc.nextInt(); // 건설순서 규칙 갯수
            int[] D = new int[N]; // 건물 당 건설 시간

            for (int d = 0; d < N; d++) {
                D[d] = sc.nextInt();
            }

            int[] inDegree = new int[N]; // 사전 건물 연결 갯수
            Map<Integer, List<Integer>> roleMap = new HashMap<>(); // key: 건물 번호, value: 다음 건설 건물
            for (int k = 0; k < K; k++) {
                int x = sc.nextInt() - 1;
                int y = sc.nextInt() - 1;

                roleMap.computeIfAbsent(x, key -> new ArrayList<>()).add(y);
                inDegree[y]++;
            }

            int W = sc.nextInt() - 1;
            getBuildingTime(W, N, D, inDegree, roleMap);
        }
    }

    private static void getBuildingTime(int W, int N, int[] D, int[] inDegree, Map<Integer, List<Integer>> roleMap) {
        int[] buildTime = new int[N];
        Queue<Integer> queue = new LinkedList<>();

        // 시작점인 경우
        for (int i = 0; i < N; i++) {
            if (inDegree[i] == 0) {
                buildTime[i] = D[i];
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int buildingNo = queue.poll();

            if (roleMap.containsKey(buildingNo)) {
                List<Integer> nextBuildings = roleMap.get(buildingNo);

                for (int nextNo : nextBuildings) {
                    buildTime[nextNo] = Math.max(buildTime[nextNo], buildTime[buildingNo] + D[nextNo]);
                    inDegree[nextNo]--;

                    if (inDegree[nextNo] == 0) {
                        queue.add(nextNo);
                    }
                }
            }
        }


        System.out.println(buildTime[W]);
    }
}