백준 1516(게임 개발) c++

문제

1516번: 게임 개발

건물의 갯수인 n이 주어지고, n개의 줄만큼 1~n 번 건물의 정보가 주어집니다.

건물의 정보는 [건물을 짓는 시간, 건물을 짓기 위해 먼저 지엉야하는 건물 번호, -1] 이렇게 주어집니다.

-1이 나오면 정보가 다 주어졌다는 의미입니다.

각 건물을 짓기 위해 최소 시간을 구하는 문제입니다.

 

각 건물은 먼저 지어져야 하는 건물이 존재합니다. 물론 없는것도 있습니다. 

따라서 이러한 정보를 바탕으로 위상정렬을 사용할 수 있습니다.

또한 "최소 시간" 이란것이 처음에는 이해하지 못했지만, 생각해 보면

예를 들어 4번 건물을 짓기 위해서는 1번 건물과 3번 건물이 먼저 세워지고, 지어야 한다고 가정합니다.

1번 건물은 짓는데 10분이 걸리고, 3번 건물은 짓는데 4분이 걸린다고 하고, 4번 건물은 짓는데 4분이 걸린다고 하면

4번 건물을 짓는데 최소 시간은 14분입니다.

왜냐하면 1번 건물과 3번 건물을 동시에 지으면 둘중에 더 오래걸리는 시간에 완성됩니다.

그리고 마지막에 현재 내가 지을 건물의 시간을 더하면 최소시간이 나오게 됩니다.

 

int cnt[501]; //위상정렬의 진입차수를 세기 위한 배열
int c[501]; //현재 건물을 짓는데 드는 비용을 저장하기 위한 배열
int ans[501]; //현재 건물을 짓는데 최소비용을 저장하기 위한 배열
vector<int>edge[501]; //위상정렬의 간선 정보를 저장하기 위한 벡터

int n;
cin >> n;

for (int i = 1; i <= n; i++) {
	int cost;
	cin >> cost;
	c[i] = cost;
	int a;
	while (1) {
	 cin >> a;
	 if (a == -1)break;
	 cnt[i]++;
	 edge[a].push_back(i);
	}
}

일단 알고리즘 자체는 위상정렬에서 다른것이 없습니다.

queue<int>q;
for (int i = 1; i <= n; i++)
	if (cnt[i] == 0) {
	q.push(i);
	ans[i] = c[i];
	}

while (!q.empty()) {
	int cur = q.front();
	q.pop();
	for (auto nxt : edge[cur]) {
		cnt[nxt]--;
		ans[nxt] = max(ans[nxt], ans[cur] + c[nxt]);
		if (cnt[nxt] == 0)q.push(nxt);
	}
}
for (int i = 1; i <= n; i++)cout << ans[i] << '\n';

먼저 cnt[i]가 0이면 가장 낮은 차수를 갖기 때문에 큐에 넣어주고, 최소비용 또한 해당 건물을 짓는데 드는 비용과 같습니다.

"최소 비용" 이란 이전에 지어진 건물들 중에 최대 시간에서 현재 내가 지을 건물의 시간을 더하면 됩니다.

즉, dp 개념이 들어갑니다.

---

전체 코드입니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>

#define INF 2000000000
using namespace std;
using ll = long long;
int cnt[501];
int c[501];
int ans[501];
vector<int>edge[501];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		int cost;
		cin >> cost;
		c[i] = cost;
		int a;
		while (1) {
			cin >> a;
			if (a == -1)break;
			cnt[i]++;
			edge[a].push_back(i);
		}
	}

	queue<int>q;
	for (int i = 1; i <= n; i++)if (cnt[i] == 0) {
		q.push(i);
		ans[i] = c[i];
	}
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (auto nxt : edge[cur]) {
			cnt[nxt]--;
			ans[nxt] = max(ans[nxt], ans[cur] + c[nxt]);
			if (cnt[nxt] == 0)q.push(nxt);
		}
	}
	for (int i = 1; i <= n; i++)cout << ans[i] << '\n';

	return 0;
}