백준 1005 ACM Craft java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/1005

(1) 조건 분석 📊

2. 코드가 나오기까지 🛠️

1. 비순환 그래프 세팅

2. 위상 정렬을 하며 다음을 구한다.
1. 진입차수를 하나 지울 때마다, 해당 빌드트리에서 걸렸던 최대 누적 시간을 현재까지 구한 최대 누적 시간과 비교하여 더 느린 걸로 갱신한다.

3. w번 건물의 누적 건축 시간을 출력한다.

(1) 시간복잡도 분석 ⏳

3. 코드 🌐

import java.util.*;
import java.io.*;

public class Main {
    static int T, V, E, W;
    static class Building {
        int idx;
        int build_time;

        public Building(int idx, int build_time){
            this.idx = idx;
            this.build_time = build_time;
        }
        @Override
        public String toString(){
            return String.format("(%d %d)", idx, build_time);
        }    }    static ArrayList<ArrayList<Building>> list = new ArrayList<>();
    static int [] degrees;
    static int [] delays;
    static int [] acc_times;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            list.clear();
            for(int j = 0; j <= V; j++){
                list.add(new ArrayList<>());
            }            delays = new int [V+1];
            degrees = new int [V+1];
            acc_times = new int [V+1];
            st = new StringTokenizer(br.readLine());
            for(int j = 1 ; j<=V; j++){
                delays[j] = Integer.parseInt(st.nextToken());
                acc_times[j] = delays[j];
            }            for(int j = 0; j < E; j++){
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                list.get(start).add(new Building(end, delays[end]));
                degrees[end]++;
            }            W = Integer.parseInt(br.readLine());
            System.out.println(topological_sort(W));
        }    }
    public static int topological_sort(int w){
        ArrayDeque<Building> aq = new ArrayDeque<>(); // 빌딩 번호 - 해당 빌딩까지 짓는 시간 포함해서 누적 시간
        // 출발점 찾기
        for(int i = 1; i <= V; i++){
            if(degrees[i] == 0) aq.add(new Building(i, delays[i]));
        }
        while (!aq.isEmpty()){
            Building now = aq.poll();
            for(int i = 0; i < list.get(now.idx).size(); i++){
                Building next = list.get(now.idx).get(i);
                degrees[next.idx]--;
                acc_times[next.idx] = Math.max(acc_times[next.idx], now.build_time + next.build_time);
                if(degrees[next.idx] == 0){
                    if(next.idx == w) return acc_times[next.idx];
                    aq.add(new Building(next.idx, acc_times[next.idx]));
                }
            }
        }
		    return acc_times[w];
    }
}

4. 트러블 슈팅 or 배운 점📝

(1) 제일 느린 건조시간을 찾기 위해 우선순위 큐 활용은 가능한가?