백준 1005 ACM Craft Java [위상정렬]

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

1005번: ACM Craft

 

위상정렬을 사용해서 풀이하는데 가중치를 줄일 때마다 건설시간 누적값을 저장한 배열을 비교해줘야한다

각 노드 별 가중치는 0 1 1 2가 되고, 건설시간 누적값은 모두 0으로 초기화 해둔다

2가 완료될 때 건설시간 누적값 11(10 + 1)을 4의 건설시간 누적값 0과 비교해서 최대값 11을 넣고

3이 완료될 때 건설시간 누적값 110(10 + 100)을 4의 건설시간 누적값 11과 비교해서 최대값 110으로 바꿔준다

출력할 때는 누적값 110과 4의 건설시간 10을 더한 값을 출력해준다

 

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            sb.append(order()).append("\n");
        }
        sb.setLength(sb.length()-1);
        System.out.println(sb);
    }

    static int order() throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] D = new int[N + 1];
        int[] degree = new int[N + 1];
        ArrayList<Integer>[] next = new ArrayList[N + 1];
        int[] time = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int n = 1; n <= N; n++) {
            D[n] = Integer.parseInt(st.nextToken());
            next[n] = new ArrayList();
        }
        for (int k = 0; k < K; k++) {
            st = new StringTokenizer(br.readLine());
            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());
            degree[Y]++;
            next[X].add(Y);
        }
        int W = Integer.parseInt(br.readLine());
        Queue<Integer> queue = new LinkedList<>();
        for (int n = 1; n <= N; n++) {
            if (degree[n] == 0) queue.add(n);
        }
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int v : next[now]) {
                degree[v]--;
                time[v] = Math.max(time[v], D[now] + time[now]);
                if (degree[v] == 0) queue.add(v);
            }
        }
        return D[W] + time[W];
    }
}