[Java] 백준 1516번 - 게임 개발

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

1516번: 게임 개발

----------------------------------------------------------------------------------------------------------------------

[문제 풀이]

이 문제는 특수알고리즘인 위상정렬을 사용해야 하는 문제였습니다.

( 위상정렬을 몰라서 한참 헤매다가 결국 풀이를 참고해서 풀었네요ㅠㅠ )

아래의 블로그가 위상정렬을 이해하는데 많은 도움이 되었습니다.

https://codingnojam.tistory.com/66

[Algorithm] 위상정렬(Topological Sort)을 Java로 구현해보자!!

예제 1번을 살펴보면 컴퓨터의 진입차수인 degree[]배열은 아래와 같습니다.

따라서 진입차수가 0인 1을 우선순위큐에 넣어주고 노드들의 의존관계를 child ArrayList에 저장하여 위상정렬을 진행합니다.

이때, 다른 일반적인 위상정렬과 다르게 게임 개발 문제에서는 모든 건물을 짓는데 최소시간을 구해야하기 때문에 건물을 짓는데 드는 시간을 저장한 배열 time[]과 해당 노드까지 오기위해 방문했던 노드들의 최대값을 저장해두는 maxTime[]을 추가하였습니다.

 

[정답 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int time[];
    public static ArrayList<ArrayList<Integer>> child = new ArrayList<ArrayList<Integer>>();
    public static int maxTime[];
    public static int degree[];
    public static PriorityQueue<Integer> pq = new PriorityQueue<>();
    public static ArrayList<Integer> start = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        time = new int[N + 1];
        maxTime = new int[N + 1];
        degree = new int[N + 1];
        for(int i=0;i<=N;i++) {
            child.add(new ArrayList<Integer>());
        }
        for(int i=1;i<=N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            int num = Integer.parseInt(st.nextToken());
            int cnt = 0;
            if(num == -1) {
                pq.offer(i);
            } else {
                while(num != -1) {
                    cnt++;
                    child.get(num).add(i);
                    num = Integer.parseInt(st.nextToken());
                }
                degree[i] = cnt;
            }
        }
        findChild();
        for(int i=1;i<=N;i++) {
            System.out.println(time[i]);
        }
    }
    public static void findChild() {
        while(!pq.isEmpty()) {
            int p = pq.poll();
            for(Integer i:child.get(p)) {
                degree[i]--;
                maxTime[i] = Math.max(maxTime[i], time[p]);
                if(degree[i] == 0) {
                    time[i] += Math.max(maxTime[i], time[p]);
                    pq.offer(i);
                }
            }
        }
    }
}