[BOJ][Java] 1516번 게임 개발

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1516

 

이 문제는 어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다는 문장에 주목해야 한다.

여기서 각 건물을 노드라고 생각한다면 그래프 형태에서 노드의 순서를 정렬하는

위상 정렬 알고리즘을 사용하는 문제라는 것을 알 수 있기 때문이다.

 

이때 위상정렬 알고리즘을 실행하면서 각 건물을 짓는데 필요한 총 시간을 업데이트해줘야 하는데

여기서는 Math.max(현재 건물에 저장된 총 시간, 이전 건물에 저장된 총 시간 + 현재 건물을 짓는데 들어가는 시간)

으로 계산해주면 된다.

 

건물을 노드라고 봤을 때

진입 차수 배열, 건물별 생산 시간, 건물 하나에 들어가는 총 시간등을 저장하는 배열이 별도로 필요하다.

package boj;

import java.util.*;
import java.io.*;

public class BOJ1516 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] sums = new int[N+1];  // 해당 건물을 짓는데 들어가는 총 시간
        int[] time = new int[N+1];  // 각 건물 짓는 시간
        int[] d = new int[N+1];     // 진입 차수
        List<List<Integer>> list = new ArrayList<>();

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

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

            while(st.hasMoreTokens()){
                int num = Integer.parseInt(st.nextToken());
                if(num == -1) break;

                d[i]++;
                list.get(num).add(i);
            }
        }

        Deque<Integer> q = new ArrayDeque<>();
        for(int i = 1; i < d.length; i++){
            if(d[i] == 0){
                q.addLast(i);
                sums[i] = time[i];
            }
        }

        while(!q.isEmpty()){
            int now = q.pollFirst();

            for(int num: list.get(now)){
                sums[num] = Math.max(sums[now] + time[num], sums[num]);
                d[num]--;
                if(d[num] == 0) q.addLast(num);
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < sums.length; i++){
            sb.append(sums[i]).append("\n");
        }

        System.out.println(sb);


    }
}