[BOJ/Gold3] 1005번 ACM Craft - JAVA[자바]

난이도 : 골드 3

유형 : 위상 정렬 / 동적 계획법

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

구현 시간 : 1시간 (못품)

 

 

 

 

 

 

 

 

문제풀이

위상 정렬 알고리즘을 공부하고 나서 처음으로 풀어본 문제이다. 노드의 방문 순서를 구현하는건 쉬웠지만, 특정 건물마다 필요한 최대 시간을 구하는 방법을 생각해내지 못했다 ㅜ

 

indegree[] 배열을 이용해 노드의 진입 차수를 저장하고, 방문마다 해당 노드의 진입 차수를 차감하여 위상 정렬을 구현했다. BFS에서 탐색 레벨마다 날짜를 계산했었던 토마토 문제가 기억이 나서 위상 정렬에도 반복마다 최대 시간을 누적하는 방식으로 최대 시간을 저장했다. 하지만 이 방법은 이전 단계에서 소요된 시간을 다음 단계에 반영하지 못하므로, 특정 노드에서 이어지는 경로를 모두 고려하지 못한 방법이였다.

 

다른 사람의 코드를 참조해보니 최대 시간은 간단히 dp[] 배열을 통해 저장하였고, 내가 작성한 알고리즘보다 훨씬 간단히 구현할 수 있었다...

 

정답 코드를 참조하려면 2차 시도 코드를 보고 넘어가면 됩니다 !

 

 

 

 

1차 시도 - 실패

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
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));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 건물의 수 = N, 건설순서 규칙 수 = K
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int[] times = new int[N + 1];                           // 노드(건물) 건설 시간
            int[] indegree = new int[N + 1];                        // 노드의 진입 차수 정보를 담는 배열
            ArrayList<Integer>[] list = new ArrayList[N + 1];       // 노드와 간선의 정보를 담는 인접 리스트

            for (int j = 1; j < N + 1; j++) {
                times[j] = Integer.parseInt(st.nextToken());
                list[j] = new ArrayList<>();
            }

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

                indegree[to]++;
                list[from].add(to);
            }

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

            int answer = 0;
            Queue<Integer> queue = new LinkedList<>();

            for (int j = 1; j < N + 1; j++) {
                if (indegree[j] == 0) {
                    queue.offer(j);
                    answer = Math.max(answer, times[j]);
                }
            }

            while (!queue.isEmpty()) {
                int size = queue.size();
                int maxTime = 0;

                for (int j = 0; j < size; j++) {
                    int poll = queue.poll();

                    for (int next : list[poll]) {
                        indegree[next]--;

                        if (indegree[next] == 0 && next <= end) {
                            queue.add(next);
                            maxTime = Math.max(maxTime, times[next]);
                        }
                    }
                }

                answer += maxTime;
            }
            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }
}

 

 

 

 

2차 시도 - 통과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
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));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 건물의 수 = N, 건설순서 규칙 수 = K
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int[] times = new int[N + 1];                           // 노드(건물) 건설 시간
            int[] indegree = new int[N + 1];                        // 노드의 진입 차수 정보를 담는 배열
            int[] dp = new int[N + 1];                              // 간 건물별 시간 계산
            ArrayList<Integer>[] list = new ArrayList[N + 1];       // 노드와 간선의 정보를 담는 인접 리스트

            for (int j = 1; j < N + 1; j++) {
                times[j] = Integer.parseInt(st.nextToken());
                list[j] = new ArrayList<>();
            }

            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                indegree[to]++;
                list[from].add(to);
            }

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

            // 위상 정렬 시작
            Queue<Integer> queue = new LinkedList<>();
            for (int j = 1; j < N + 1; j++) {
                if (indegree[j] == 0) {
                    queue.offer(j);
                    dp[j] = times[j];
                }
            }

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

                for (int next : list[poll]) {
                    indegree[next]--;
                    dp[next] = Math.max(dp[next], dp[poll] + times[next]);

                    if (indegree[next] == 0) {
                        queue.add(next);
                    }
                }
            }
            sb.append(dp[end]).append("\n");
        }
        System.out.println(sb);
    }
}