1516번 게임 개발

백준 온라인 저지 1516번 게임 개발

---

문제 출처 : https://www.acmicpc.net/problem/1516

풀이 과정

이번 문제는 정점들 간에 순서를 가지고 있으므로 위상 정렬을 구현해서 각 건물을 짓는데 걸리는 시간을 구하는 문제입니다.

위상 정렬에 관해서는 조만간 정리해서 포스팅하도록 하겠습니다.

어떤 건물의 시간을 구할 때 그 건물을 짓기 위해 먼저 지어져야 할 건물들은 없을 수도 있고, 한 개가 있을 수도 있고 여러 개가 있을 수도 있습니다. 어떤 건물이 지어지는데 걸리는 시간을 구할 때 우선적으로 지어져야 할 건물이 2개 이상일 경우에는 어떻게 최소시간을 구해야 할까요? 

예를 들면 C 건물이 지어지는데 걸리는 시간을 구하려고 할 때 C 건물을 짓기 위해선 A 건물과 B 건물들이 지어져 있어야한다고 가정해보겠습니다. 

C 건물을 짓는데 걸리는 시간은 10+25 (A+C), 20+25(B+C)가 있습니다. 최소 시간을 구하기 위해 둘 중 어떤 값으로 답을 갱신해야 할까요? 문제에서 최소 시간을 구하라고 해서 작은 값으로 갱신해서는 안됩니다. C는 A와 B 둘 다 지어져 있어야 하는데 A(10초)가 지어져있다고 해도 B(20초)가 지어져 있지 않기 때문에 C를 지을 수 없기 때문입니다. 따라서 먼저 지어져야하는 건물들이 지어지고 자신의 건물이 건설되기 위해서는 가장 오래 걸리는 시간을 기준으로 계산해야 합니다.

즉 위상 정렬을 구현하고 그 위상 정렬에 의해 구해지는 최대 시간을 구하는것이 문제에서 요구하는 최소 시간이 되겠습니다~

소스코드

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(in.readLine());
		ArrayList vertex[] = new ArrayList[n + 1];
		int dist[] = new int[n + 1];
		int degree[] = new int[n + 1];
		int ans[] = new int[n + 1];
		Queue q = new LinkedList<>();

		for (int i = 1; i <= n; i++)
			vertex[i] = new ArrayList<>();

		for (int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			int d = Integer.parseInt(st.nextToken());
			dist[i] = ans[i] = d;

			int v;
			while ((v = Integer.parseInt(st.nextToken())) != -1) {
				vertex[v].add(i);
				degree[i]++;
			}
		}

		for (int i = 1; i <= n; i++)
			if (degree[i] == 0)
				q.add(i);

		while (!q.isEmpty()) {
			int here = q.poll();
			for (int there : vertex[here]) {
				ans[there] = Math.max(ans[there], ans[here] + dist[there]);
				if (--degree[there] == 0)
					q.add(there);
			}

		}

		for (int i = 1; i <= n; i++) {
			out.write(ans[i] + "\n");
		}
		out.close();
	}
}