[BOJ 2056] 작업 (Java)

#문제

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

2056번: 작업

 

#풀이

위상정렬 알고리즘을 이용해서 푼다. 

 

#소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ2056 {

    public static int N;
    public static ArrayList<Integer>[] adjs;
    public static int[] indegs, needTimes, times;
    public static void input() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        indegs = new int[N+1]; // 들어오는 간선의 개수를 담을 배열
        needTimes = new int[N+1]; // 각 작업 별 소요 시간 저장
        times = new int[N+1]; // 선행 작업 시간 + 현재 작업 시간 합을 담을 배열
        adjs = new ArrayList[N+1]; // 인접 노드 리스트
        for(int i = 0; i <= N; i ++){
            adjs[i] = new ArrayList<Integer>();
        }

        StringTokenizer st = null;
        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            needTimes[i] = Integer.parseInt(st.nextToken());
            st.nextToken();
            while(st.hasMoreTokens()){
                adjs[Integer.parseInt(st.nextToken())].add(i);
                indegs[i]++;
            }
        }
    }

    public static void topologicalSort(){
        Queue<Integer> que = new LinkedList<Integer>();
        for(int i = 1; i <= N; i++){
            if(indegs[i] == 0){ // 들어오는 간선이 없는 경우, 시작점
                que.offer(i);
                times[i] = needTimes[i]; // 시작점의 경과 시간은 시작점의 소요시간과 동일
            }
        }

        while(!que.isEmpty()){
            int node = que.poll(); 
            for(int adj : adjs[node]){
                indegs[adj]--; // 해당 노드와 인접한 노드의 간선 개수를 감소시킨다.
               
                // 인접 노드의 선행 작업 시간 + 인접 노드 작업 시간의 합의 최대값
                times[adj] = Math.max(times[adj], times[node] + needTimes[adj]);
                
                if(indegs[adj] == 0){ // 들어오는 간선이 없을 경우 queue에 넣는다.
                    que.offer(adj);
                }
            }
        }

		
        int ans = Integer.MIN_VALUE;
        for(int i = 1; i < times.length; i++){
            ans = Math.max(ans, times[i]);
            // 그래프가 여러 개일 수 있기 때문에 전체 노드를 확인한다.
        }
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        topologicalSort();
    }
}