[백준] 1516번 : 게임 개발 - 자바(JAVA)

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

1516번: 게임 개발

 

문제 해석

모든 건물이 완성되기 위한 시간을 구해야 합니다.

건물에는 순서가 존재할 수 있습니다.

예를 들어 A건물을 지어야지 B건물을 지을 수 있는 경우가 존재하기 때문에 이점을 고려해야 합니다.

 

건물의 수와 각 건물의 짓는 데 걸리는 시간과 해당 건물을 짓기 위해 지어져야 하는 건물들의 번호가 주어집니다.

짓기 위해 지어야 하는 건물은 여러 개가 존재할 수 있습니다.

각 줄은 -1으로 끝납니다.

 

문제 풀이 전 설계

건물의 종류 수가 최대 500개 입니다.

따라서 O(N^2)을 사용해도 문제가 없을 것 같습니다.

 

아이디어는 건물의 짓는 데 걸리는시간을 buildtimes 배열에 넣어두고 의존하는 건물들이 모두 지어진 경우 해당 건물들이 지어진 최대 시간 + 현재 건물을 짓는데 걸리는 시간을 업데이트합니다.

 

buildtimes를 DP처럼 이용하는 문제 같습니다.

DP인 이유는 값을 계속 업데이트하며 이 값을 기준으로 해당 건물이 의존하는 건물들이 지어진지 확인하기 때문입니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] buildtimes = new int[N + 1];
        int result = 0;

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

        int time = 0, buildingNum = 0;
        StringTokenizer st = null;

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            time = Integer.parseInt(st.nextToken());
            buildings.get(i).add(time);
            while (st.hasMoreTokens()) {
                buildingNum = Integer.parseInt(st.nextToken());
                buildings.get(i).add(buildingNum);
            }
        }
        //입력 끝

        //기다리는건물들을 저장하고 순차적으로 검사
        Queue<Integer> buildWaiting = new LinkedList<Integer>();
        for (int i = 1; i <= N; i++) {
            buildWaiting.add(i);
        }

        //모든 건물을 짓는 것이 가능한 입력만 주어지기 때문에 가능
        while (!buildWaiting.isEmpty()) {
            int currentBuilding = buildWaiting.poll();
            ArrayList<Integer> currentInfo = buildings.get(currentBuilding);
            int needTime = currentInfo.get(0);

            boolean isBuild = true;
            int maxTime = 0;

            for(int i=1; i<currentInfo.size(); i++){
                int tempBuildingNum = currentInfo.get(i);

                if(tempBuildingNum== -1){
                    continue;
                }

                //먼저 지어져야 하는 건물이 지어지지 않은 경우
                if(buildtimes[tempBuildingNum] == 0){
                    isBuild = false;
                    break;
                }

                maxTime = Math.max(maxTime, buildtimes[tempBuildingNum]);
            }

            //건물을 짓지 못한다면 큐에 다시 넣고 continue
            if(!isBuild){
                buildWaiting.add(currentBuilding);
                continue;
            }



            //건물을 지을 수 있다면
            buildtimes[currentBuilding] = maxTime + needTime;

        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(buildtimes[i] + "\n");
        }
        System.out.println(sb.toString());

    }
}