[백준] 1516 게임 개발

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/1516

(1) 조건 분석 📊

• 각 건물마다 그것을 지으려면 선행해서 완성해야하는 건물이 있을 수 있다.
  (마치 스타크래프트나 임진록 같은 게임을 하면 배럭 전에 벙커를 지을 수 없는 것과 마찬가지)
• 각 건물마다 그것을 지을 수 있는 최소 시간을 구하라.

2. 코드가 나오기까지 🛠️

KEY WORD: 위상정렬, 우선순위 큐

(0) 집중 포인트 잡고 가기

이번 문제에서는 집중해야할 포인트와 그러지 말아야할 포인트가 나뉜다.

먼저 집중해야할 포인트는 "각 건물마다 그것을 짓기 위해서는 선행되어 지어져야 하는 건물이 존재할 수 있다" 라는 것이다. 이것은 해당 문제가 위상 정렬 을 써야 함을 소리치고 있다.

괜히 집중했다간 문제 풀이의 방향성을 잃어버리는 포인트는 바로 '최소'라는 말이다. 선행되어야 하는 작업이 끝나는 시점이 바로 최소 시점임으로 위상정렬 풀이 방식에서는 해당 시점 특정이 기본적으로 된다. 따라서 굳이 해당 단어에 집중해 방향성을 잡을 필요가 없다.

(1) 현실 상황처럼 생각하기 (우선순위 큐 적용점)

만약 우리가 진짜 스타크래프트와 같이 빌드 트리가 존재하는 게임을 한다고 가정해보자. 건물 Z를 짓기 위해서는 건물 A,B,C,D가 선행되어 건조되어야 한다고 가정했을 때, 어떻게 플레이 하겠는가?

당연히, 선행 건조 건물 중 가장 빠르게 지을 수 있는 건물부터 해서 차례대로 해치울 것이다. 그것이

1. 만약 선행 건물들 중에서도 선행, 후행 건물이 나뉠 경우, 별도의 코드 없이 이를 해결할 수 있고,
2. 현실적으로 현재 건조하고픈 건물 Z를 짓는 가장 빠른 길이기

때문이다.

그렇다면, 가장 빠르게 지을 수 있는 건물이라는 것은 어떻게 정의내리면 될까? 필자는 다음과 같이 우선순위를 두어 정의했다.

1. 현 시점에서 즉시 지을 수 있는 건물이 가장 빠르게 지을 수 있는 건물이다.
   (즉, 선행되어 지어져야할 건물이 더 이상 남지 않았다.)
2. 1번을 충족하는 건물이 여러 개일 경우, 누적된 건축 시간이 가장 짧은 건물이 가장 빠르게 지을 수 있는 건물이다.

10초 걸리는 건물 A 먼저 짓고 15초 걸리는 건물 C를 짓는 행위나, 이 반대 행위나 최종적인 시간은 같지 않은가? 하고 의문을 가질 수 있지만. 2번은 뒤에 나올 반례를 해결해주는 규칙이라 필수적이다.

이를 위해 위상정렬에 기본적으로 쓰이는 일반 큐 대신 우선순위 큐 를 활용했다.

원래의 위상 정렬 의미처럼 큐에 삽입된 정점은 더 이상 사용하지 않은 진입차수가 없는 것이라 할 수 있다. (해당 문제로 풀어 쓰면, 즉시 지을 수 있는 건물)
그럼 큐에 있는 값들은 기본적으로 위의 1번 규칙을 충족시키는 값들이다. 여기서 누적 건축축 시간에 따른 정렬을 위해 우선순위 큐를 *건조 시간이 빠른 *

(2) 누적 시간을 기록하는 타이밍

해당 문제의 요구사항은 특정 건물의 건축에 걸리는 최소시간 이다. 이는 당연히 본 건물 자체의 건축 시간 + 선행 건물들의 건축 시간일 것이다. 해당 문제에서는 건축 시간을 누적 시키는 타이밍이 중요하다.

시간을 누적시키는 타이밍은 큐에 특정 정점을 삽입하는 순간이다.
큐에 특정 정점이 삽입된다는 것은 _즉시 건축이 가능함_을 의미한다. 건물을 지을 수 있다는 것은 다른 말로, 이미 건축 최소 시간 측정이 끝났다는 것도 된다.

만약 진입 간선을 없애는 모든 순간에 그 간선의 가중치를 누적시킨다면 어떻게 될까?

문제에 나온 예시를 도면화 해보았다. 이제 모든 진입 간선 삭제 타이밍에 그것의 목적지 정점의 누적 코스트를 올려보겠다.

출발점인 1에서의 간선을 다 없애고, 목적지 정점의 비용을 누적 시켰다. 다음을 진행해보겠다.

3번의 간선을 없앴더니, 4번 건물 건축의 최소 시간이 24가 되어버렸다. 하지만 올바른 풀이를 생각해 보면1번과 3번을 짓는데 걸리는 14초 + 본인을 짓는데 걸리는 4초가 되어서 총 18번이 맞다.

만약 올바른 풀이처럼 큐에 넣는 타이밍에만 그것의 가중치를 누적했으면 1-> 3 -> 4 차례로 비용이 누적됨을 표현할 수 있음으로, 중복 없이 해결할 수 있다.

(3) 우선순위 큐가 꼭 필요한 이유

우선순위 큐가 꼭 필요한 경우는 하나의 목적지로 가는 방법이 2개 이상인 경우 이다.

위의 예시에서는 6번으로 가는 경우가 2가지로 나뉜다. 만약 규칙 2번의 (누적된 건축 시간이 빠른 순 재정렬이 없다면)

건조시간이 비교적 더 걸리는 1번 루트를 먼저 사용하여 결과를 저장하고, 그 후에 2번 루트를 씀으로서 필수적으로 걸려야 하는 시간보다 더 짧은 시간으로 건축 최소 시간이 단축되어버릴 수 있다. 해당 값은 유효하지 않은 값임으로 당연히 틀렸다.

반면 우선순위 큐를 활용한다면, 큐의 머리에서 나오는 노드는 당연히 건조시간이 더 빠른 2번 루트임으로, 항상 더 시간이 오래걸리는 쪽으로 덮어써진다.

(4) 시간복잡도 분석 ⏳

위상정렬의 내부는 BFS로 이루어져있기 때문에 기본적인 위상정렬의 시간복잡도는 $O(V+E)$ 이다. 다만 해당 문제는 우선순위 큐를 써서 매 삽입마다 $O(logN)$ (N은 큐 안의 값의 개수) 가 더 든다. 따라서 최종적인 시간복잡도는 다음과 같다.

$$
O( (V+E)* logN)
$$ V는 정점의 개수, E는 간선의 개수, N은 우선순위 큐안에 값의 개수
N이 500임으로, 그래프를 완전그래프라고 봐도 E는 25,000을 넘지 못한다. N은 최대 정점의 개수만큼 담겨 있으므로 아무리 이론적인 최대치를 계산해도,
25,500 * 22.36067977 밖에 되지 않는다.

3. 코드 🌐

(1) SUDO CODE 💬

+ 0. 초기화 (인접리스트, 진입 차수 배열, 누적 건축 시간 배열)
+ 1. 우선순위 큐 장착한 BFS 돌리기
-     (1) 진입 차수가 0인 값은 큐에 넣는다. (정점 번호 + 누적 시간)
-     (2) 내부는 건축시간이 빠른 순으로 정렬한다.
-     (3) 큐에 넣는 순간 누적 건축 시간 배열에 지금까지 누적된 값을 누적 시간 배열에 저장한다.
+ 2. 누적 시간 배열을 일렬로 출력한다.

(2) JAVA CODE ☕

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

public class Main {

    static class Building {
        int index;
        int time;

        public Building(int i, int t){
            this.index = i;
            this.time = t;
        }
    }
    static int N;
    static ArrayList<Building> [] lists;
    static int [] inDegree;
    static int [] completeTime;

    public static void main(String[] args) throws Exception {
        init();
        topological_graph();
        print();

    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        lists = new ArrayList [N+1];
        inDegree = new int [N+1];
        completeTime = new int [N+1];

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

        for(int i = 1; i<= N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 지금 짓는 건물의 번호
            int now = i;
            int time = Integer.parseInt(st.nextToken());
            completeTime[now] = time;

            // 인접리스트 초기화 (후행정점의 배열에 선행 정점들을 Building class로 저장) 
            while(st.hasMoreTokens()){
                // 먼저 지어져야 하는 건물의 번호
                int prev = Integer.parseInt(st.nextToken());
                if(prev == -1) break;
                lists[prev].add(new Building(now, time));
                inDegree[now]++;
            }
        }
    }

    public static void topological_graph() {
        PriorityQueue<Building> pq = new PriorityQueue<>((o1, o2) -> (o1.time - o2.time));
        // 초기값 넣어주기
        // 진입 차수 배열인 inDegree가 -1 이면 이미 방문한 배열임.
        for(int i = 1; i <= N; i++){
            if(inDegree[i] == 0){
                pq.add(new Building(i, completeTime[i]));
                inDegree[i] = -1;
            }
        }

        while(!pq.isEmpty()) {
            Building prev = pq.poll();

            for(int i = 0; i < lists[prev.index].size(); i++){
                Building now = lists[prev.index].get(i);
                inDegree[now.index]--;

                if(inDegree[now.index] == 0) {
                    inDegree[now.index] = -1;
                    completeTime[now.index] += prev.time;
                    pq.add(new Building(now.index, completeTime[now.index]));
                }
            }
        } 
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 1; i < N + 1; i ++){
            bw.write(String.valueOf(completeTime[i]) + "\n");
        }

        bw.flush();
        bw.close();
    }
}

4. 트러블 슈팅 or 배운 점📝

실수를 총 2가지 했다.

• while문을 큐가 비어있을 때만 동작하게 한 거
• 우선순위 큐를 내림차순으로 정렬한 것

둘 다 내가 집중력이 떨어져 있을 때 자주하는 실수이다. 반복하지 말자.^~^

A. 2025-05-17 재복습을 하며

• 최초 풀이에서는 우선순위 큐가 필요한 이유를 생각하지 않고 푼 거 같다.
  우선순위 큐가 필요한 이유는 하나의 정점으로 오는 진입 차수 후보지 중 비용이 가장 큰 녀석을 고르기 위해서 이다. 해당 문제는 하나의 건물을 짓기 위한 선행 건물의 개수가 몇 개이든, 동시에 지을 수 있으므로, 선행 건물들 중에 가장 건축 시간이 느린 녀석의 건축 시간 + 자신의 건축 시간을 해야 한다.
• 이것을 가장 가독성 있게 구현하는 방법은 큐 삽입 시점 + 후보군 중 가장 느린 건축시간 확인 시점을 동일하게 하는 것이다.
• 물론 일반 큐로도 풀 수 있지만, 위의 시점이 어그러지면서, 코드를 따로 작성 및 관리해야 하는 관점이 있다.
• 반면 우선순위 큐를 활용하면, 우선순위가 작은 차순이 먼저오게 queue를 정렬해서, 큐 삽입 시점과 후보군 중 가장 느린 건축 시간 확인 및 갱신 시점을 맞출 수 있다.

5. 최종 요약

Q. 누적 건축 시간 업데이트의 올바른 시점은?

특정 건물이 건축 되어서 큐안에 들어가는 순간, 그 건물의 누적 시간을 업데이트 해야함.
그것이 문제를 실생활적으로 생각했을 때도 자연스럽고, 건축이 완료된 것만 누적 시간을 업데이트 하니까, 중복 계산이 이루어질 이유가 없음

Q. 우선순위 큐 대신 일반 큐를 쓰면 생기는 문제점은?

유효하지 않은 최소 시간으로 덮어써지는 경우가 생긴다.

---

Relevace Framing 🧩

관련된 개념 : [[위상정렬]], [[우선순위 큐]]