[백준]2056: 작업 - JAVA

[백준]2056: 작업

풀이

선행 관계에 맞추어 모든 작업을 완료하는 시간을 구하는 위상정렬 문제였다. 오랜만에 푸는 위상정렬 문제여서 중간에 조금 헤메며 풀었다. 

 

문제 난이도는 어렵지 않은 수준의 위상정렬 문제였다. 위상정렬 알고리즘을 사용하여 모든 노드를 선행 관계에 맞추어 작업을 마무리 할 수 있는 최소 시간을 구해주었다.

 

각각 구한 최소시간에서 가장 큰 값을 선택하면 그 값이 모든 작업을 완료 했을 때의 시간이 되므로 반복문을 사용하여 가장 큰 값을 찾아주었다.

 

코드

import java.util.*;
 
public class Main {
    
    static ArrayList<Integer>[] list;
    static int n;
    static int[] cost;
    static int[] indegree;
    static int[] times;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        
        list = new ArrayList[n + 1];
        indegree = new int[n + 1];
        times = new int[n + 1];
         for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
            times[i] = scan.nextInt();
            indegree[i] = scan.nextInt();
    
            for(int j = 0; j < indegree[i]; j++) {
                list[scan.nextInt()].add(i);
            }
        }
        
        cost = new int[n + 1];
        topologySort();
        
        int result = 0;
        for(int i = 1; i <= n; i++) {
            result = Math.max(result, cost[i]);
        }
        System.out.println(result);
    }
    
    public static void topologySort() {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= n; i++) {
            if(indegree[i] == 0) {
                q.offer(i);
                cost[i] = times[i];
            }
        }
        
        while(!q.isEmpty()) {
            int current = q.poll();
            
            for(int i = 0; i < list[current].size(); i++) {
                int next = list[current].get(i);
                cost[next] = Math.max(cost[current] + times[next], cost[next]);
                indegree[next]--;
                if(indegree[next] == 0) q.offer(next);
            }
        }
    }
}