[백준]1516: 게임 개발 - JAVA

[백준]1516: 게임 개발

풀이

이전에 지어야할 건물들을 모두 건설하며 모든 건물을 짓는데 걸리는 시간을 반환하는 문제로 위상정렬 알고리즘을 활용하였다.

 

입력받는 정보는 진입간선이 되는 정보가 아닌, 진출간선이 되는 정보이므로 입력 받은 건물의 번호에 현재 건물 정보를 add해서 위상정렬 알고리즘을 사용할 수 있도록 적절하게 입력해 주었다.

 

각각의 건물들의 비용을 저장하는 cost, 각각의 건물을 완성하여 짓는데 걸리는 최소 비용 result, 진입 간선을 기록하는 indegree와 간선의 정보를 저장하는 list를 사용하였다.

 

건물을 짓는데 걸리는 총 비용을 계산하는 부분에서는 다음과 같이 계산해 주었다.

result[next] = Math.max(result[next], result[currnet] + cost[next]

다음 건물을 짓기 위해선 이전의 건물을 모두 지어야 다음 건물을 지을 수 있기 때문이다.

 

입력 받는 부분, 총 비용을 계산하는 부분만 잘 처리해 주면 위상정렬 알고리즘을 활용하여 쉽게 풀 수 있다.

 

코드

import java.util.*;
 
public class Main {
 
    static int n;
    static ArrayList<Integer>[] list;
    static int[] cost, indegree, result;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        list = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
 
        cost = new int[n + 1];
        indegree = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            cost[i] = scan.nextInt();
            while(true) {
                int build = scan.nextInt();
                if(build == -1) break;
                list[build].add(i);
                indegree[i]++;
            }
        }
 
        result = new int[n + 1];
        topologySort();
 
        for(int i = 1; i <= n; i++) {
            System.out.println(result[i]);
        }
    }
 
    public static void topologySort() {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= n; i++) {
            if(indegree[i] == 0) {
                q.offer(i);
                result[i] = cost[i];
            }
        }
 
        while(!q.isEmpty()) {
            int current = q.poll();
 
            for(int i = 0; i < list[current].size(); i++) {
                int next = list[current].get(i);
                result[next] = Math.max(result[next], result[current] + cost[next]);
                indegree[next]--;
                if(indegree[next] == 0) q.offer(next);
            }
        }
    }