BOJ 1516번 게임 개발 ( 위상 정렬 , DP ) JAVA

BOJ 1516번 게임 개발 ( 위상 정렬 , DP ) JAVA

---

풀이

위상 정렬을 통해 어떤 건물을 먼저 지어야 될지를 결정지어준다.

이 때, 중요한 것은 ans배열을 하나 선언하여, 현재까지 계산된 시간보다 더 오래 걸리는지를 체크해줘야 한다.

 

링크

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

 

소스 코드

---

package boj;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// 게임 개발
public class Boj1516 {
    static int n;
    static int[] parentNum;
    static int[] cost;
    static int[] ans;
    static Queue<Integer> q = new LinkedList<>();
    static ArrayList<ArrayList<Integer>> map = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        parentNum = new int[n + 1];
        cost = new int[n + 1];
        ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            map.add(new ArrayList<>());
        }
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            while (true) {
                int temp = sc.nextInt();
                if (temp == -1)
                    break;
                if (cnt == 0) {
                    cost[i] = temp;
                    cnt++;
                    continue;
                }
                map.get(temp).add(i);
                parentNum[i]++;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (parentNum[i] == 0) {
                ans[i] += cost[i];
                q.add(i);
            }
        }
        int time = 0;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int next : map.get(cur)) {
                parentNum[next]--;
                ans[next] = Math.max(ans[cur] + cost[next], ans[next]);
                if (parentNum[next] == 0) {
                    q.add(next);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            System.out.println(ans[i]);
        }
        System.out.println();
    }
}