백준 1516번: 게임 개발 (C++)

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

1516번: 게임 개발

어떤 건물이 지어지기까지 특정한 건물이 지어져야 한다는 전제 조건이 존재한다.

즉 건물이 지어지는 데에 순서가 있다는 뜻이다.

 

"N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다."라고 되어있는데 여기서 오해를 하여 해석한 부분이 어떤 건물을 짓는데 걸리는 최소 시간으로 해석했다.

 

>> 즉, 최단 경로처럼 이해했다는 말이고, 이 문제는 "어떤 건물이 지어지기까지 특정한 건물이 지어져야 한다는 전제 조건" 다음을 만족시키면서 코드를 구현해야 한다.

 

오해했던 부분은 코드에 주석으로 달아두었다.

 

[AC 코드]

#include <iostream>
#include <vector>
#include <queue>
#define INF 50000001
using namespace std;

int n;
int inDegree[501];
int delay[501];
int dist[501];
vector<int> adj[501];

void topologicalSort() {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) {
			dist[i] = delay[i];
			q.push(i);
		}
	}

	while (!q.empty()) {
		int now = q.front();

		q.pop();
		for (int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i];

			// 이 부분을 원래 dist를 INF로 초기화시키고
			// min 값으로 구하려 했었다.
			// 각 건물들이 next라는 건물을 짓기 전에 지어야 한다면
			// 그 모든 시간 중 가장 오래 걸리는 시간을 갱신해야 하므로
			// dist가 0인 상태에서 시간들을 갱신해야 한다.
			dist[next] = max(dist[next], dist[now] + delay[next]);
			if (--inDegree[next] == 0) {
				q.push(next);
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> delay[i];

		int v;
		while (true) {
			cin >> v;
			if (v == -1) break;
			adj[v].push_back(i);
			inDegree[i]++;
		}
	}

	topologicalSort();

	for (int i = 1; i <= n; i++) {
		cout << dist[i] << '\n';
	}

	return 0;
}