[백준] 1516번. 게임 개발(JAVA)

문제

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

---

풀이(30분)

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

public class Main {

    // 배열에는 완공되어야 하는 개수 -> 이게 0이 된 것을 큐?에 넣는다.
    // 큐는 시간이 늘어남에 따라 완공할 수 있는 건물을 추적한다.
    // 건물 완성 배열과완공 건물갯수도 추적해야할듯?
    // 맵에는 <int, List<int>>로 어떤 건물을 완공하면 지을 수 있는 건물들을 추적한다.
    static int n;
    static int[][] building;
    static boolean[] completed;
    static HashMap<Integer, List<Integer>> list = new HashMap<>();
    static PriorityQueue<Construction> constructionSchedule = new PriorityQueue<>();

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

        n = Integer.parseInt(br.readLine());
        building = new int[3][n]; // 0행은 걸리는 시간, 1행은 선행 건물의 개수, // 2행은 완성된 시간
        completed = new boolean[n];

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            building[0][i] = time;
            int input = Integer.parseInt(st.nextToken());
            while(input != -1){
                list.computeIfAbsent(input - 1, k -> new ArrayList<>()).add(i);
                building[1][i] += 1;
                input = Integer.parseInt(st.nextToken());
            }
            if(building[1][i] == 0){ // 선행 건물이 없다면 바로 큐에 추가
                constructionSchedule.add(new Construction(building[0][i], i));
            }
        }

        int time = 0;
        while(!constructionSchedule.isEmpty()){
            Construction cur = constructionSchedule.poll(); // 가장 먼저 지을 수 있는 것 하나 꺼내옴
            time = cur.finishTime;
            if(completed[cur.buildingIdx]){ // 이미 지은 건물이면 패스
                continue;
            }
            // 아직 안 지은 건물이라면
            completed[cur.buildingIdx] = true; // 지은 건물로 체크
            building[2][cur.buildingIdx] = time; // 완성 시간 체크
            if(list.get(cur.buildingIdx) == null){ // 후행 건물이 없다면 패스
                continue;
            }
            for(int i : list.get(cur.buildingIdx)){ // 후행 건물들에 대하여
                if(building[1][i] > 1){ // 아직 더 짓어야 할 건물이 있다면
                    building[1][i] -= 1; // 선행 건물 한개만 제거
                    continue;
                }
                if(building[1][i] == 1){ // 마지막 선행 건물이었다면
                    building[1][i] -= 1; // 선행 건물 한개 제거
                    constructionSchedule.add(new Construction(time + building[0][i], i)); // 큐에 추가
                }
            }
        }

        for(int i = 0; i < n; i++){ // 건물 별 완공 시간 출력
            System.out.println(building[2][i]);
        }
    }



    static class Construction implements Comparable<Construction>{
        int finishTime, buildingIdx;

        public Construction(int finishTime, int buildingIdx){
            this.finishTime = finishTime;
            this.buildingIdx = buildingIdx;
        }

        @Override
        public int compareTo(Construction o) { // 완성 시간이 빠른 것부터 정렬
            return this.finishTime - o.finishTime;
        }
    }

}

---

문제 풀이 전략

 

열을 건물의 번호로, 행을 각 역할에 맞는 값으로 입력을 받아 초기화한다.

0행은 걸리는 시간, 1행은 선행 건물의 개수, 2행은 완성된 시간을 의미한다.

 

입력을 받는 과정은 다음과 같다.

1. 0행에 건물을 짓는 데 걸리는 시간을 저장한다.

2. 키 : 선행 건물, 밸류 : 선행 건물을 필요로 하는 건물들에 추가한다.

3. 만약, 선행 건물이 없다면 우선순위 큐에 바로 추가한다.

-> 우선순위 큐는 건물 완공 시간을 기준으로 정렬된다.

 

큐가 비어있을 때까지 다음 과정을 반복한다.

1. 큐에서 다음 완공시킬 건물을 뽑는다.

2. 시간을 해당 건물 완공 시간으로 설정한다.

3. 만약, 이미 완공된 건물이라면 다음으로 넘어간다. (초기 한 번을 빼면 큐에 들어올 일이 없으므로 2 뒤에 3을 해도 문제가 발생하지 않는다.)

4. 건물을 완공한다.

5. 후행 건물이 없다면 큐를 반복한다.

6. 후행 건물이 있다면 후행 건물들에 대하여 아래와 같은 과정을 반복한다.

6-1. 아직 더 짓어야 할 건물이 있다면, 선행 건물 한개만 제거하고 큐를 반복한다.

6-2. 마지막 선행 건물이었다면, 선행 건물을 제거하고, 큐에 추가한다.(이제 건설할 수 있다는 뜻이다.)

-> 큐에 추가할 때는 현재 시간 + 건물 건설 시간을 시간으로 넣는다.