[BOJ] 2056. 작업

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

접근 방법

문제에서 작업을 하는데에 있어서 순서가 있다고 하였다.

작업을 하기 전에 끝내야 할 것이 있으므로 위상 정렬을 사용하기로 했다.

degree 가 0 ( 선행 조건을 다 수행을 하였다 ) 이 된 값 들을 queue에 넣어주는 방법.

그리고 tmp 배열을 사용한 이유는 각 작업을 끝내기 위해 필요한 누적 소요 시간을 저장을 따로 해줘야 되기 때문이다.

Need Know

1. 위상 정렬

전체 코드 ( Java )

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N;
    static int[] time;
    static int[] tmp;
    static int ans;
    static int[] degree;
    static ArrayList<Integer>[] preceding;
    static Queue<Integer> queue;
    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException{
        N = Integer.parseInt(br.readLine());
        queue = new LinkedList<>();
        time = new int[N+1];
        tmp = new int[N+1];
        degree = new int[N+1];
        preceding = new ArrayList[N+1];

        for(int i=1; i<N+1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            tmp[i] = time[i] = Integer.parseInt(st.nextToken());
            preceding[i] = new ArrayList<>();

            int precedingCnt = Integer.parseInt(st.nextToken());

            for(int k=0; k<precedingCnt; k++){
                int vertex = Integer.parseInt(st.nextToken());
                preceding[vertex].add(i);
                degree[i] ++;
            }
        }
        for(int i=1; i<N+1; i++){
            if( degree[i] == 0 ){
                queue.add(i);
            }
        }
    }
    static void solve() throws IOException {
        while(!queue.isEmpty()){
            int vertex = queue.poll();
            for(int i=0; i< preceding[vertex].size(); i++){
                int nv = preceding[vertex].get(i);

                if(time[nv] < tmp[nv] + time[vertex]){
                    time[nv] = tmp[nv] + time[vertex];
                }
                degree[nv]--;
                if(degree[nv]==0){
                    queue.add(nv);
                }
            }
        }
        for(int i=1; i<N+1; i++){
            if(ans < time[i]){
                ans = time[i];
            }
        }
        bw.write(ans+"");
    }
}