b1005. ACMcraft

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

 

 

 

이 문제는 위상 정렬을 이용해서 특정 건물을

완성하는 데 필요한 총 건설 시간을 구하는 문제다.

각 건물은 다른 건물들이 먼저 완성되어야만 지을 수 있는 조건이 있고,

이런 순서를 바탕으로 누적 시간을 계산해야 한다.

먼저 prepare 메서드에서 입력값을 처리한다.

건물 개수와 건설 순서 규칙을 입력받고, inDegree 배열에 각 건물의 진입 차수를 저장한다.

buildCost 배열은 각 건물의 초기 건설 시간으로 설정한다.

list 배열에는 선행 건물 정보를 넣어서 다음 건물로 이어지는 관계를 저장한다.

main 메서드에서 테스트 케이스마다 prepare를 호출한 뒤,

진입 차수가 0인 건물들을 큐에 넣어 시작점을 잡는다.

큐에서 건물을 하나씩 꺼내면서 위상 정렬을 수행하고,

현재 건물의 건설 비용을 기준으로 연결된 다음 건물들의 누적 비용을

buildCost에 업데이트한다.

이렇게 해서 목표 건물 W에 도달하면 buildCost[W] 값을 출력하여 해결하였다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static Queue<Integer> q;
    private static int[] inDegree, times, buildCost;
    private static boolean[] isVisited;
    private static int N, K, T, W, answer;
    private static ArrayList<Integer>[] list;
    private static BufferedReader br;

    private static void prepare() throws IOException {
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        K = Integer.parseInt(input[1]);
        isVisited = new boolean[N];
        inDegree = new int[N];
        buildCost = new int[N];
        q = new ArrayDeque<>();
        answer = 0;
        times = Arrays
                .stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        list = new ArrayList[N];

        for (int i = 0; i < N; i++) {
            list[i] = new ArrayList<>();
            inDegree[i] = 0;
            buildCost[i] = times[i]; // 초기화 시 각 건물의 건설 시간으로 시작
        }

        for (int i = 0; i < K; i++) {
            int[] arr = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            list[arr[0] - 1].add(arr[1] - 1);
            inDegree[arr[1] - 1]++;
        }

        W = Integer.parseInt(br.readLine()) - 1;
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            prepare();

            // 초기 진입 차수가 0인 건물들을 큐에 넣기
            for (int i = 0; i < N; i++) {
                if (inDegree[i] == 0) {
                    q.add(i);
                }
            }

            while (!q.isEmpty()) {
                int now = q.poll();
                isVisited[now] = true;

                // 종료 조건: 목표 건물을 짓기 위한 누적 시간 계산 후 출력
                if (now == W) {
                    answer = buildCost[now];
                    sb.append(answer).append("\n");
                    break;
                }

                // 현재 건물을 통해 연결된 다음 건물들의 비용 업데이트
                for (int next : list[now]) {
                    buildCost[next] = Math.max(buildCost[next], buildCost[now] + times[next]);
                    inDegree[next]--;
                    if (inDegree[next] == 0) {
                        q.add(next); // 진입 차수가 0이 된 건물을 큐에 추가
                    }
                }
            }
        }
        System.out.println(sb);
    }
}

 

 

 

 내코드보다 더 효율적으로 작성한 사람의 코드를 발견하였다.
그사람의 코드도 공유하고 설명하겠다.

두 코드 모두 위상 정렬을 사용해 특정 건물을 완성하기 위한 최소 시간을 구하는 문제를 해결한다.

그러나 초기화 방식, 배열 처리, 그리고 코드 최적화 부분에서 몇 가지 차이점이 있다.

 

먼저, 내 코드에서는 건물 번호가 0부터 시작해 배열 인덱스를 조정하고 사용한다.

반면에 상대 코드에서는 건물 번호를 1부터 시작해 N+1 크기로 배열을 선언하여, 인덱스 조정 없이 건물 번호와 배열 인덱스를 일치시켜 간단하게 활용한다.

 

또한, 아래 코드는 building 배열과 buildCost 배열을 구분해

각각 기본 건설 시간과 누적 건설 비용을 관리한다.

 

buildCost를 초기화하지 않고 topologySort 메서드 내에서

진입 차수가 0인 건물들만 초기 비용을 설정해 효율성을 높였다.

위상 정렬 부분에서도 약간의 차이가 있다.

내 코드에서는 isVisited 배열을 사용해 방문 여부를 관리하는 반면,

상대 코드는 inDegree 배열로만 진입 차수를 관리해 메모리와 시간 낭비를 줄였다.

 

상대 코드에서는 topologySort 메서드에서

한 번 큐에 진입 차수 0인 건물들을 모두 추가하고,

다음 건물로 이동할 때마다 연결 관계와 비용을 업데이트해

다음 진입 차수가 0인 건물을 바로 큐에 넣는 방식이다.

이는 반복적인 진입 차수 확인 과정을 줄이고,

큐 관리가 동적으로 이루어지므로 더 효율적이었다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, K, W;
    static ArrayList<Integer>[] list; // 연결 간선 정보
    static int[] building; // 각 건물의 건설 비용 정보
    static int[] indegree;
    static int[] buildCost; // 각 건물까지 도달하는 데 필요한 최대 건설 비용

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

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

            building = new int[N + 1];
            list = new ArrayList[N + 1];
            for (int i = 1; i <= N; i++) {
                list[i] = new ArrayList<>();
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                building[i] = Integer.parseInt(st.nextToken());
            }

            indegree = new int[N + 1];
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());
                list[X].add(Y);
                indegree[Y]++;
            }

            W = Integer.parseInt(br.readLine()); // 건설해야 할 건물의 번호
            buildCost = new int[N + 1];
            topologySort();
            sb.append(buildCost[W]).append("\n");
        }
        System.out.print(sb);
    }

    public static void topologySort() {
        Queue<Integer> q = new LinkedList<>();

        // 초기 진입 차수가 0인 건물을 큐에 삽입하고, 해당 건물의 건설 비용을 설정
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                buildCost[i] = building[i];
                q.offer(i);
            }
        }

        // 위상 정렬을 통한 건설 비용 계산
        while (!q.isEmpty()) {
            int current = q.poll();

            for (int next : list[current]) {
                buildCost[next] = Math.max(buildCost[next], buildCost[current] + building[next]);
                indegree[next]--;

                // 진입 차수가 0이 되면 큐에 추가
                if (indegree[next] == 0) {
                    q.offer(next);
                }
            }
        }
    }
}