자바(백준) 1005 ACM Craft

오답 노트 & 새로 알게 된 점

입력이 많은 문제일수록 천천히 읽고 순차적으로 풀 생각을 해야한다.

또한, 기능 별로 메서드를 잘 나눠야한다!!

 

처음 문제 접근을 말해보겠다.

입력을 다 한 뒤, 일반 위상정렬처럼 문제를 풀었다.

 

그런데 여기서 시간을 어떻게 구할지 생각하기 위해 예제를 손으로 직접 써보았다.

time[i]는 i번째 건물을 지을 때 걸리는 시간이다.

time[7]을 구할 때는 time[5]와 time[6]의 최댓값에 build[7]을 더한 값이다.

왜?

7번 건물은 5번, 6번 건물이 모두 지어져야 지을 수 있기 때문이다.

 

그렇다면 7번 건물의 시간을 구할 때 5, 6번 건물들을 어떻게 가져올 수 있을까라는 생각을 했다.

위상정렬에서는 start -> end 로 가는 방향만 연결리스트에 넣었다.

하지만 7번 건물에 어떤 건물들이 전제조건으로 있는지 알기 위해 end -> start로 가는 연결리스트(B)를 하나 더 만들었다.

 

그래서 deg가 0이 되는 순간에 q에 집어넣고, 그 때 건물을 짓기 위해 지어야하는 건물들을 B 연결리스트를 통해 알 수 있었다.

 

얻은 건물들을 탐색하면서 build[7]과 더했을 떄 가장 최댓값을 구하면 된다.

 

하지만 이게 끝이 아니었다.

 

초기값을 넣어주어야 한다.

 

초기값은 처음에 큐에 넣을 때(위상정렬의 시작점), time[i] = build[i]를 해주어야한다.

위상정렬의 시작점은 건물을 짓고 시작하기 때문이다.

 

---

코드

package Sort;
 
import java.io.*;
import java.util.*;
 
public class BOJ1005 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, K;
    static int build[];
    static int target;
    static ArrayList<Integer> A[];
    static int deg[];
    static int time[];
    static ArrayList<Integer> B[];
    public static void main(String[] args) throws IOException {
        input();
    }
 
    static void pro() {
        Queue<Integer> q = new ArrayDeque<>();
 
        for(int i = 1; i <= N; i++) {
            if (deg[i] == 0) {
                q.offer(i);
                time[i] = build[i];
            }
        }
 
 
        while (!q.isEmpty()) {
            int m = q.poll();
 
            for(int n : A[m]){
                deg[n]--;
                if(deg[n] == 0) {
                    q.offer(n);
                    for(int z : B[n]){
                        time[n] = Math.max(time[z] + build[n], time[n]);
                    }
                }
            }
        }
 
        System.out.println(time[target]);
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int test = atoi(br.readLine());
 
        while (test-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
 
            N = atoi(st.nextToken());
            K = atoi(st.nextToken());
 
            build = new int[N + 1];
            A = new ArrayList[N + 1];
            B = new ArrayList[N + 1];
            time = new int[N + 1];
            for (int i = 0; i <= N; i++) {
                A[i] = new ArrayList<>();
                B[i] = new ArrayList<>();
            }
            deg = new int[N + 1];
 
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) build[i] = atoi(st.nextToken());
 
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int s = atoi(st.nextToken());
                int e = atoi(st.nextToken());
 
                A[s].add(e);
                B[e].add(s);
                deg[e]++;
            }
 
            target = atoi(br.readLine());
 
            pro();
        }
    }
}