위상정렬 (Topological Sort)

package boj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class TopologicalSort {
	/*
	 * BOJ 1516 게임 개발
	 * https://www.acmicpc.net/problem/1516
	 */

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/seminar/boj1516.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer ST;
		
		
		int N = Integer.parseInt(br.readLine());
		int[] time = new int[N+1];
		int[] result = new int[N+1];
		int[] inDegree = new int[N+1];
		
		
		ArrayList[] outList = new ArrayList[N+1];
		for (int i = 1; i <= N; i++){
			outList[i] = new ArrayList();
		}
		
		for (int i = 1; i <= N; i++){
			ST = new StringTokenizer(br.readLine());
			
			int n = Integer.parseInt(ST.nextToken());
			time[i] = n;
			result[i] = n;
			while(ST.hasMoreTokens()){
				int next = Integer.parseInt(ST.nextToken());
				if(next == -1) break;
				outList[next].add(i);
				inDegree[i]++;
			}
		}
		
		Queue que = new LinkedList();
		for (int i = 1; i <= N; i++){
			if (inDegree[i] == 0){
				que.add(i);
			}
		}
		
		while (!que.isEmpty()){
			int cur = que.poll();
			for (int next : outList[cur]){
				result[next] = Math.max(result[next], result[cur]+time[next]);
				inDegree[next]--;
				if (inDegree[next] == 0){
					que.add(next);
				}
			}
		}
		
		for (int i = 1; i <= N; i++){
			bw.write(result[i]+"\n");
		}
		
		
		
		br.close();
		bw.flush();
		bw.close();
	}

}