[Algo] 백준 1516 게임 개발 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/1516

메모리 : 22260KB

시간 : 288ms

언어 : Java 11

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
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));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        Queue<Integer> q = new LinkedList<>();
        List<List<Integer>> list = new ArrayList<>();
        int[] time = new int[N + 1];
        int[] ans = new int[N + 1];
        int[] cnt = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            int num = Integer.parseInt(st.nextToken());
            if (num == -1) {
                ans[i] = time[i];
                q.add(i);
            } else {
                cnt[i]++;
                list.get(num).add(i);
                while (true) {
                    num = Integer.parseInt(st.nextToken());
                    if (num == -1)
                        break;
                    cnt[i]++;
                    list.get(num).add(i);
                }
            }
        }
        while (!q.isEmpty()) {
            int now = q.poll();
            for (int next : list.get(now)) {
                cnt[next]--;
                ans[next] = Math.max(ans[now] + time[next], ans[next]);
                if (cnt[next] == 0)
                    q.add(next);
            }
        }
        for (int i = 1; i <= N; i++) {
            sb.append(ans[i]).append("\n");
        }
        System.out.print(sb);
    }
}

풀이

순서를 지켜가며 해결해야하는 문제이기때문에 위상정렬을 이용해 풀 수 있다. 어떤 건물 A를 짓기 전 지어야 하는 건물들을 이어보면 트리를 만들 수 있다. 문제에 케이스는 모두 건물을 지을 수 있는 경우로 주어진다고 했으니 맨 처음 조건없이 지을 수 있는 건물들을 시작으로 하나씩 지어나가면 된다. 건물을 지어가며 Queue에 넣어주면 되는데, cnt배열을 사용하지 않았을 때 시간초과가 발생한다. Queue에는 건물이 한 번씩만 들어가야하는데 이를 위해 조건이 만족된 건물만 넣어주기 위해 cnt배열을 사용한다. 앞선 건물이 완공되면 즉 cnt가 0이면 공사를 할 수 있는 순서가 되어 Queue에 입장하는 것이다.

++ "위상"이라는 말이 궁금해서 사전을 찾아보니 관계 속에서 가지는 위치라는 말이었다. 위상수학이라는 것도 있었다. 뭔가 항상 애매한 개념이었는데 뜻을 알고나니 오래 기억할것같은 기분😎