[Java] 백준 2056번 -작업

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

2056번: 작업

[문제 풀이]

이전에 풀었던 위상정렬을 사용한 백준 게임개발 문제랑 거의 비슷한 문제였습니다.

풀이는 게임개발 포스팅을 첨부하도록 하겠습니다.

https://j-su2.tistory.com/4?category=1016202

[Java] 백준 1516번 - 게임 개발

[정답 코드]

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

public class Main {
    public static int N;
    public static int[] degree;
    public static int[] time;
    public static int[] maxTime;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    public static PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        degree = new int[N];
        time = new int[N];
        maxTime = new int[N];
        for(int i=0;i<N;i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            // 의존 관계수 받음
            degree[i] = Integer.parseInt(st.nextToken());
            if (degree[i] == 0) {
                pq.add(i);
            }
            for (int j = 0; j < degree[i]; j++) {
                // 0번~N-1번으로 넣기 위해서 -1 해줌
                int num = Integer.parseInt(st.nextToken());
                graph.get(num - 1).add(i);
            }
        }
        findTime();
        Arrays.sort(time);
        System.out.println(time[N-1]);
    }
    public static void findTime() {
        while(!pq.isEmpty()) {
            int p = pq.poll();
            for(Integer i:graph.get(p)) {
                maxTime[i] = Math.max(maxTime[i], time[p]);
                degree[i] -= 1;
                if(degree[i] == 0) {
                    time[i] += maxTime[i];
                    pq.add(i);
                }
            }
        }
    }
}