[BOJ]1516 - 게임 개발 (G3)

문제 링크

1516-게임 개발

입력

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다.
다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다.
건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자.
각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다.
모든 건물을 짓는 것이 가능한 입력만 주어진다.

출력

N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다.

문제 풀이

우선 ArrayList까지 만들어 우선 순위에 있는 건물들의 정보를 저장했지만
그 이후에 어떻게 해야하나 생각을 했지만 답이 안나와서 찾아보다보니
위상정렬 알고리즘을 알고있다면 쉽게 풀 수 있는 문제였다.

각 건물들을 짓기위해 걸리는 시간을 저장한 times
건물을 완성하기 위해 필요한 최소비용을 저장할 result
진입 간선의 갯수를 저장하기 위한 indegree
간선들의 정보를 저장하는 buildings를 사용했다.

위상 정렬에 대한 설명은 여기를 참조했고
문제를 보니 알고리즘에 대한 기본적인 문제인듯?싶다

result[next] = Math.max(result[next], result[cur] + times[next])

위의 코드는 총 비용을 계산하기 위한 식으로 다음 건물을 짓기 위해서는 이전의 건물들을 모두 지어야한다는 개념을 이용한 부분이다.

이 부분이 조금 헷갈렸지만 이 부분만 처리한다면 끝!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int[] times, indegree, result;
    static ArrayList<Integer>[] buildings;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        buildings = new ArrayList[n + 1];
        indegree = new int[n + 1];
        times = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            buildings[i] = new ArrayList<>();
        }

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            times[i] = Integer.parseInt(st.nextToken());
            while (true) {
                int tmp = Integer.parseInt(st.nextToken());
                if (tmp == -1) break;
                buildings[tmp].add(i);
                indegree[i]++;
            }
        }

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


    // 위상정렬
    public static void topologySort() {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
        	// 진입 차수가 0이라면 큐에 추가
            if (indegree[i] == 0) {
                queue.offer(i);
            }
            result[i] = times[i];
        }

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : buildings[cur]) {
                indegree[next]--;	// 연결된 간선 삭제
                result[next] = Math.max(result[next], result[cur] + times[next]);
                
                if (indegree[next] == 0) queue.offer(next);
            }
        }
    }
}