백준,2056,위상정렬,DAG,그래프

Problem2056.java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int N;
	static int[] cost;
	static int[] in;
	static int[] result;
	static LinkedList<Integer>[] list;
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		cost = new int[N+1];
		in = new int[N+1];
		list = new LinkedList[N+1];
		for(int i = 1; i <= N; i++) {
			list[i] = new LinkedList<>();
		}
		
		result = new int[N+1];
		
		for(int i = 1; i <= N; i++) {
			cost[i] = sc.nextInt();
			
			int num = sc.nextInt();
			for(int k = 0; k < num; k++) {
				int next = sc.nextInt();
				list[next].add(i);
				in[i]++;
			}
		}
		
		sc.close();
		
		Queue<Integer> queue = new LinkedList<>();
		for(int i = 1; i <= N; i++) {
			if(in[i] == 0) {
				queue.add(i);
				result[i] = cost[i];
			}
		}
		
		while(!queue.isEmpty()) {
			
			int current = queue.poll();
			
			for(int next : list[current]) {
				
				if(result[next] < result[current] + cost[next]) {
					result[next] = result[current] + cost[next];
				}
				
				if(--in[next] == 0) {
					queue.add(next);
				}
			}
		}
		
//		for(int n : result)
//			System.out.printf("%d ", n);
//		System.out.println();
		
		int ans = 0;
		for (int i = 1; i <= N; i++) {
			ans = Math.max(ans, result[i]);
		}
		System.out.println(ans);
	}
}