[BOJ] 1516. 게임 개발

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

접근 방법

전에 풀었던 문제와 비슷하다.

시간을 계속 누적하면서 더하면 된다.

이 때 시간의 최댓값이 나와줘야 하므로 밑의 코드처럼 체크를 해주었다.

if(ans[nv] < build_time[nv] + ans[vertex]){
                    ans[nv] = build_time[nv] + ans[vertex];
                }

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 StringTokenizer st;

    static int N;
    static int[] build_time;
    static int[] build_rule_cnt;
    static int[] ans;
    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());

        preceding = new ArrayList[N+1];
        for(int i=1; i<N+1; i++){
            preceding[i] = new ArrayList<>();
        }
        build_rule_cnt = new int[N+1];
        build_time = new int[N+1];
        ans = new int[N+1];
        queue = new LinkedList<>();

        for(int i=1; i<N+1; i++){
            st = new StringTokenizer(br.readLine());
            build_time[i] = Integer.parseInt(st.nextToken());
            ans[i] = build_time[i];
            while(true){
                int x = Integer.parseInt(st.nextToken());
                if( x == -1 ) break;
                build_rule_cnt[i] ++;
                preceding[x].add(i);
            }
        }
    }
    static void solve() throws IOException {

        for(int i=1; i<N+1; i++){
            if(build_rule_cnt[i] == 0){
                queue.add(i);
            }
        }

        while(!queue.isEmpty()){
            int vertex = queue.poll();
            for(int i=0; i<preceding[vertex].size(); i++){
                int nv = preceding[vertex].get(i);

                if(ans[nv] < build_time[nv] + ans[vertex]){
                    ans[nv] = build_time[nv] + ans[vertex];
                }

                build_rule_cnt[nv]--;

                if(build_rule_cnt[nv] == 0){
                    queue.add(nv);
                }
            }
        }
        for(int i=1; i<N+1; i++){
            bw.write(ans[i] + "\n");
        }
    }
}