[BOJ 1516 // C++] 게임 개발

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1516번 문제인 게임 개발이다.
문제는 아래 링크를 확인하자.

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

1516번: 게임 개발

각 건물을 노드로, 건물 사이에 주어지는 관계를 에지로 갖는 그래프를 생각해보자.

항상 모든 건물의 건설이 가능한 입력만 주어지므로, 주어지는 입력으로 만들어지는 방향그래프는 DAG가 될 것이다.

이 DAG 위에서 위상정렬순으로 각 건물이 완성되는 시간을 조사하는 것으로 문제를 해결할 수 있다.

 

구체적으로, 두 건물 사이에 짓는 순서가 주어졌을 때 나중에 짓게 되는 건물은 빨라봐야 (먼저 짓게 되는 건물을 짓기 시작할 수 있는 가장 빠른 시간) + (먼저 짓게 되는 건물을 짓는 시간)에 짓기 시작할 수 있다. 이를 이용하여 관계식을 세우면 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> G[501];
int indegree[501];
int construction[501];
int ans[501];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; cin >> construction[i] >> x;
		while (x > 0) {
			indegree[i]++;
			G[x].emplace_back(i);
			cin >> x;
		}
	}

	queue<int> que;
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) que.push(i);
	}
	while (!que.empty()) {
		int current = que.front(); que.pop();
		ans[current] += construction[current];
		for (auto node : G[current]) {
			ans[node] = max(ans[node], ans[current]);
			indegree[node]--;
			if (indegree[node] == 0) que.push(node);
		}
	}

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