[백준 온라인 저지] 1516. 게임 개발

게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다.

편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정하자.

 

1. 입력

- 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다.

- 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다.

- 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자.

- 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. 모든 건물을 짓는 것이 가능한 입력만 주어진다.

 

2. 출력

- N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다.

 

3. 예제

 

4. 코드

import java.util.*;
import java.io.*;
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));
        int n = Integer.valueOf(br.readLine()); // 건물의 수
        int[] times = new int[n+1];    // 건물을 짓는 데 필요한 시간
        int[] indegree = new int[n+1]; // i번째 건물보다 먼저 지어야하는 건물 수
        Queue<Integer> q = new LinkedList<>(); // 정렬에 필요한 큐
        int[] result = new int[n+1]; // i번 건물을 짓는 데 걸리는 총 시간
        
        List<List<Integer>> graph = new ArrayList<List<Integer>>(); // 건물 짓는 순서를 담을 그래프
        for(int i=0 ; i<=n ; i++)         // i번째 건물을 지은 후 graph.get(i)의 건물 짓기 가능
            graph.add(new ArrayList<>()); // 편의를 위해 0번째는 사용하지 않을 예정
        
        for(int i=1 ; i<=n ; i++){
            StringTokenizer token = new StringTokenizer(br.readLine());
            times[i] = Integer.valueOf(token.nextToken()); // i번 건물을 짓는데 필요한 시간
            while(true){
                int num = Integer.valueOf(token.nextToken()); // i번 건물 전에 지어야 하는 건물
                if(num==-1) break;
                graph.get(num).add(i);
                indegree[i]++;                
            }
        }
        
        for(int i=1 ; i<=n ; i++)
            if(indegree[i]==0){
                result[i] = times[i];
                q.add(i);
            }
    
        for(int i=1 ; i<=n ; i++) {
            int cur = q.remove();
            for(int j : graph.get(cur)){
                result[j] = Math.max(result[j], result[cur]+times[j]);
                if(--indegree[j]==0) q.add(j);
            }            
        }
        
        for(int i=1 ; i<=n ; i++)
            bw.write(result[i]+"\n");
        bw.flush(); bw.close();
    }
}