BOJ_1516 : 게임 개발

👉 문제링크

---

---

🔸 문제 분석 🔸

• 스타크레프트 같은 게임에서 각 건물을 짓는데 필요한 최소 시간을 구해보자.
• N개의 건물 별 짓는 시간과 먼저 지어져야 하는 건물의 번호가 주어진다.

🔸 문제 풀이 🔸

• 선행 되어야 하는 번호가 주어지므로 위상 정렬(Topology Sort)을 활용해 풀이할 수 있다.
• 선행 건물 건설 직후 해당 건물을 짓는데, 선행 건물이 여러개일 경우 순서를 정할 수 없다.
• 따라서 선행 건물이 지어지는 시간의 최대값 + 현재 건물을 짓는 시간을 구한다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public 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));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] d = new int[N + 1];
        int[] time = new int[N + 1];

        ArrayList<Integer>[] adjList = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            time[i] = a;

            while ((a = Integer.parseInt(st.nextToken())) > -1) {
                adjList[a].add(i);
                d[i]++;
            }
        }

        Queue<Integer> que = new ArrayDeque<>();
        int[] answer = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            if (d[i] == 0) {
                que.offer(i);
                answer[i] = time[i];
            }
        }

        while (!que.isEmpty()) {
            int a = que.poll();
            for (int i : adjList[a]) {
                answer[i] = Math.max(answer[i], answer[a] + time[i]);
                if (--d[i] == 0) {
                    que.offer(i);
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            sb.append(answer[i]).append('\n');
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

🔸 코드 해석 🔸

• N개의 건물의 지어지는 시간을 time, 진입 차수를 d 배열에 저장한다.
• 위상 정렬을 위해 간선 정보를 ArrayList 배열 adjList에 저장한다.
• 큐를 만들고, 현재 진입 차수가 0인 건물의 건설 시간을 바로 정답 배열 answer에 저장하고, 건물 번호는 큐에 넣는다.
• 큐가 빌 때까지 계산을 반복한다.
  • 큐에서 나온 건물의 다음 건설 건물의 시간을 answer에 저장한다.
  • 이때, 기존 건설 시간과 현재 건물 직후로 짓는 건설 시간 중 큰 값을 저장한다.
  • 만약 진입 차수가 0이 되었다면 큐에 넣는다.
• 정답 배열에 저장 된 건설 시간을 출력한다.

---

🔸 end 🔸

• 부분적인 선행 작업 정보가 나왔으니, 위상 정렬이 바로 떠올랐다.
• 다만, 첫 풀이에서는 진입 차수가 0이 되었을때 answer[i]에 값을 저장하는 방식으로 했는데 틀렸다.
• 건물이 동시에 지어질 수 있으므로, 선행 작업 중 더 오래걸리는 값으로 계산해야 했다.