백준 1005번 ACM Craft (JAVA)

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

1005번: ACM Craft

 

해당 문제는 그래프의 순서가 존재하여 위상정렬을 사용하여 문제를 풀었습니다.

저는 각각의 노드에 들어오는 최대 시간을 구하였습니다. 각각의 노드에서 다른 노드로 갈 때 시간들을 구했고, 이를 time이라는 배열에 넣어서 관리하였습니다. 이 중 최대 값을 구하여 문제를 해결하였습니다. 

 

package BOJ.Graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1005 {
    static int spendTime[];
    static int count[];
    static int time[];
    static int target;
    static List<Integer> map[];
    static int n, k;
    static int cal(){
//        System.out.println("------");
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1 ; i <= n ; i++){
            if(count[i] == 0){
                q.offer(i);
            }
        }
        while(!q.isEmpty()){
            int now = q.poll();
            int nowTime = time[now] + spendTime[now];
//            System.out.println(now+" "+nowTime);
            if(now == target){
                return nowTime;
            }
            for(int i = 0 ; i < map[now].size(); i++){
                int next = map[now].get(i);
                time[next] = Math.max(time[next],nowTime);
                if(--count[next] == 0){
                    q.offer(next);
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int test = stoi.apply(st.nextToken());
        for(int t = 0 ; t < test ; t++){
            st = new StringTokenizer(br.readLine()," ");
            n = stoi.apply(st.nextToken());
            k = stoi.apply(st.nextToken());
            st = new StringTokenizer(br.readLine()," ");

            spendTime = new int[n+1];
            count = new int[n+1];
            time = new int[n+1];
            map = new List[n+1];

            for(int i = 1 ; i <= n ; i++){
                map[i] = new ArrayList<>();
            }

            for(int i = 1 ; i <= n ; i++){
                spendTime[i] = stoi.apply(st.nextToken());
            }
            for(int i = 0 ; i < k; i++){
                st = new StringTokenizer(br.readLine()," ");
                int a = stoi.apply(st.nextToken());
                int b = stoi.apply(st.nextToken());
                map[a].add(b);
                count[b]++;
            }
            st = new StringTokenizer(br.readLine()," ");
            target = stoi.apply(st.nextToken());
            System.out.println(cal());
        }
    }
}