작업 [백준 2056][골드4][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

2056번: 작업

이게 왜 골드 4지

줄 세우기, 문제집 과 같은 위상정렬 문제.

가장 오래 걸리는 시간을 구해야 하므로

result 배열을 만들어 현재 노드와 다음 노드의 작업량을 저장시켰다.

문제를 이해하기 힘들었다.ㅠ

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

public class 작업 {
	static int N; // 그래프 정점의 수
    static int M; // 간선의 수
    static ArrayList<ArrayList<Integer>> graph;
    static int[] Link;
    static int[] cost;
    static int[] result;
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        
        graph = new ArrayList<>();
        
        Link =   new int[N + 1]; // 간선의 수에 대한 배열
        cost =   new int[N + 1]; // 비용에 대한 배열
        result = new int[N + 1]; // 비용을 더할 결과를 저장할 배열
        
        for (int i = 0; i < N+1; i++) {
        	graph.add(new ArrayList<Integer>());
		}
        
        for (int i = 1; i <= N; i++) {
			cost[i] = sc.nextInt();
			M = sc.nextInt();
			
			for (int j = 0; j < M; j++) {
				int node = sc.nextInt();
				graph.get(i).add(node);
				Link[node]++;
			}
		}
        Sort();
	}
	public static void Sort() {
		Queue<Integer> q = new LinkedList<>();

		for (int i = 1; i <= N; i++) {
			if(Link[i] == 0) { 
				q.add(i);
				result[i] = cost[i];
			}
		}
		
		while(!q.isEmpty()) {
			int node = q.poll();
			
			for (int nextNode : graph.get(node)) {
				Link[nextNode]--; //연결된 링크 해제
				
				//다음 링크에게 비용을 더한값을 저장
				if(result[nextNode] < result[node] + cost[nextNode]) { 
					result[nextNode] = result[node] + cost[nextNode]; }
				
				if(Link[nextNode] == 0) {
					q.add(nextNode);
				}

			}
		}
		int ans = Integer.MIN_VALUE;
		for (int i = 1; i <= N; i++) {
			ans = Math.max(ans, result[i]);
		}
		System.out.println(ans);
	}
	


}