[백준] 2056 작업 - Graph Theory / Java

• 문제 링크

2056번: 작업

 

• 풀이 과정

각각의 작업이 수행되기 전에 선행되어야 할 작업의 수를 진입 차수로써 inDegree 배열에,

해당 작업의 소요 시간을 cost 배열에 저장한다.

 

작업 i 에 대하여 inDegree[i] == 0 인 작업을 큐에 삽입하고

해당 작업 소요 시간을 res 배열에 저장하여 위상 정렬을 수행한다.

 

현재 작업의 후행 작업들의 inDegree 값을 1씩 감소시키면서 inDegree 가 0 일 경우 큐에 삽입한다.

이때 2개 이상의 선행 작업이 동시에 수행될 수 있는데,

후행 작업의 현재까지 누적된 소요시간과 현재 수행되고 있는 선행 작업의 소요시간 + 후행 작업의 소요시간

을 비교 및 큰 값을 갱신하여 저장한다. (res[v] = Math.max(res[v], res[node] + cost[v]))

 

이렇게 모든 작업의 누적된 소요시간 중 가장 큰 값이 작업을 완료하기 위한 최소 시간이 되며, 

이 경우 Stream 을 사용하여 구한 최대값을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        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[] inDegree = new int[n + 1];
        int[] cost = new int[n + 1];

        List<List<Integer>> list = new ArrayList<>();

        for (int i = 0; i <= n; i++)
            list.add(new ArrayList<>());

        for (int v = 1; v <= n; v++) {
            st = new StringTokenizer(br.readLine());
            cost[v] = Integer.parseInt(st.nextToken());

            int cnt = Integer.parseInt(st.nextToken());
            for (int i = 0; i < cnt; i++) {
                int precede = Integer.parseInt(st.nextToken());

                list.get(precede).add(v);
                inDegree[v]++;
            }
        }

        Queue<Integer> q = new LinkedList<>();
        int[] res = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0){
                q.offer(i);
                res[i] = cost[i];
            }
        }

        while (!q.isEmpty()) {
            int node = q.poll();

            for (int v : list.get(node)) {
                inDegree[v]--;
                res[v] = Math.max(res[v], res[node] + cost[v]);

                if (inDegree[v] == 0)
                    q.offer(v);
            }
        }

        bw.write(Arrays.stream(res).max().getAsInt() + "\n");
        bw.flush();
    }

}