1516 - 게임 개발 (Java)

 

---

 

문제

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

 

 

풀이

 

위상정렬을 활용해 풀어야 하는 문제이다.

 

처음엔 위상정렬 문제인지 모르고 막 풀었다가.. 호되게 당했다.

 

사실 위상정렬을 공부하고 나면, 선후관계가 있는 이 문제를 어떻게 풀어야하는지 감이온다.

 

단지 여기서 가장 큰 문제는, 동시에 건물을 지을 수 있다는 점이다.

 

A와 B건물은 선행 건물이 없고, C 건물은 선행건물로 A B 건물이 있다고 하자.

 

A와 B는 동시에 건설이 시작될테고 더 오래걸리는 20 이 소요되고, 그 때 C를 건설할 수 있을것이다.

 

이런 부분을 고려해야하는데 A와 B는 같은 수준의 레벨이라고 했을때 C 입장에서 더 오래걸리는 시간을 택해야 한다.

 

식을 만들어보면 [다음 건물 총 건축시간] = Max(다음건물 총 건축시간, 현재건물 총 건축시간 + 다음건물 건축시간) 

 

와 같이 표현할 수 있다.

 

건축시간과 총 건축시간을 구분해야하는데, 건축시간은 그 건물만 짓는데 소요되는 시간이고, 총 건축시간은 선행 건물들을 다 포함했을때의 건축시간이다.

 

위상정렬을 수행하면서 총 건축시간을 계속 계산하면서 문제를 풀이하면 된다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {


    public void solution() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // Key, List => Key 건물을 짓기 위해 필요한 건물들
        int n = Integer.parseInt(br.readLine());

        Map<Integer, List<Integer>> techTree = new HashMap<>();
        int[] buildTime = new int[n+1];
        int[] inDegree = new int[n+1];
        int[] answer = new int[n+1];

        for (int i = 1; i <= n; i++) {
            techTree.put(i, new ArrayList<>());
            inDegree[i] = 0;
        }

        // 건물들의 정보를 입력받는다.
        for (int i = 0; i < n; i++) {
            int target = i + 1;

            String[] numbers = br.readLine().split(" ");
            buildTime[target] = Integer.parseInt(numbers[0]);
            answer[target] = Integer.parseInt(numbers[0]);

            // 해당 건물을 짓기 위해 선행되어야 하는 건물들
            for (int j = 1; j < numbers.length - 1; j++) {
                int preBuilding = Integer.parseInt(numbers[j]);
                techTree.get(preBuilding).add(target);
                inDegree[target] += 1; // 진입차수 증가.
            }
        }

        // 위상정렬 수행
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if(inDegree[i] == 0){ // 진입차수가 0인 값들을 넣어준다.
                queue.addLast(i);
            }
        }

        while (!queue.isEmpty()) {
            int target = queue.removeFirst();

            for (int val : techTree.get(target)) {
                inDegree[val] -= 1;
                
                // 같은 회차인 경우에는 max 값으로 처리한다.
                answer[val] = Math.max(answer[val], answer[target] + buildTime[val]); 
                if(inDegree[val] == 0){
                    queue.addLast(val);
                }
            }
        }

        for(int i=1; i<=n; i++){
            System.out.println(answer[i]);
        }
    }


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}