#백준_2056 작업 - Java 자바

#유형 : 위상 정렬

#난이도 : 골드 4

# 큐를 통해 위상 정렬 알고리즘을 구현하면 되는 문제였다. 위상 정렬 알고리즘이란 싸이클이 허용되지 않는 가정하에 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 알고리즘이다. 진입 차수가 0인 노드를 큐에 넣어가며 선행 처리가 끝난(진입 차수가 0이된)노드에서 방문 가능한 노드들을 차례로 방문해주며 시간을 더해주면 된다.

package bj;
 
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 p2056 {
    static int N;
    static int cost[], arr[], pre[];
    static ArrayList<Integer> arrList[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cost = new int[N+1];
        arr = new int[N+1];
        pre = new int[N+1];
        arrList = new ArrayList[N+1];
        for(int i=0; i<=N; i++)
            arrList[i] = new ArrayList<>();
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            cost[i] = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            for(int j=0; j<val; j++) {
                int prev = Integer.parseInt(st.nextToken());
                arrList[prev].add(i);
                pre[i]++;
            }
        }
        
        
        bfs();
        int maxValue = 0;
        for(int i : arr) {
            maxValue = Math.max(maxValue, i);
        }
        System.out.println(maxValue);
    }
    private static void bfs() {
        // TODO Auto-generated method stub
        
        Queue<Integer> queue = new LinkedList<Integer>();
        
        // 진입 차수가 0인 노드를 큐에 넣어준다.
        for(int i=1; i<=N; i++) {
            if(pre[i] == 0) {
                queue.add(i);
                arr[i] = cost[i];
            }
        }
        
        while(!queue.isEmpty()) { 
            int num = queue.poll();
            // 진입 차수가 0 인 노드를 선행으로 갖는 노드들에 대해 수행해준다.
            for(int i=0; i<arrList[num].size(); i++) {
                int next = arrList[num].get(i);
                if(arr[next] < arr[num] + cost[next])
                    arr[next] = arr[num] + cost[next];
                if(--pre[next] == 0) {
                    queue.add(next);
                }
            }
        }
        
    }
}