[백준]게임 개발(1516)

문제 링크 : [백준]게임 개발(1516)

1516번: 게임 개발

문제 설명

게임에서 건설할 수 있는 건물 N개가 존재하고, 그 건물을 짓는데 필요한 시간이 주어집니다.

또한 그 건물을 짓기 위해서는 먼저 지어져야 할 건물들의 관계가 주어집니다.

각각의 건물을 짓는데 필요한 최소한의 시간을 구하세요.

입력

N(건물의 갯수, 1 <= N <= 500)

T_i P_ij -1(T_i : i번째 건물을 짓는데 걸리는 시간, P_ij : i번째 건물을 짓기전에 지어져야 하는 건물 번호, -1이 나올때 까지 반복)

5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

 

출력

10
20
14
18
17

 

카테고리

#위상정렬

 

시간 복잡도 상한

O(N³)

해결 방법

1. 건물이 지어지기 위해서는 선행되어야 하는 건물들이 지어져야 합니다.
2. 각 건물마다 지어져야 하는 건물의 갯수를 세었을 때, 그 수가 0이면 바로 지어질 수 있는 건물입니다.
3. 그런 건물들이 지어지면, 그 건물들이 지어지기를 기다리는 건물들은 더 이상 그 건물이 지어지길 기다릴 필요가 없습니다.
4. 따라서 그 건물이 지어지기를 기다리는 건물들의 2에서 센 카운트를 1 줄여줍니다.
5. 카운트가 0으로 줄었다면, 그 건물도 바로 지어질 수 있기 때문에 건물을 짓기 시작합니다.
6. 단, 이미 이전에 지어진 건물이 지어질 때 걸린 시간 이후에 짓기 시작하기 때문에, 짓기 시작한 건물의 건설 시간에 앞선 시간을 더해줍니다.
7. 위와 같은 행동을 반복하면 됩니다.
8. 위상정렬을 이용해 위 풀이 방법을 해결할 수 있습니다.

시간복잡도

O(N²) (엣지의 갯수)

코드

#include<cstdio>
#include<queue>
#include<vector>

using namespace std;
struct {
	int c;
	int max;
} b[502];

int N, max_val = 0, x, y, temp;
vector<int> v[502];
int ind[502];
queue<int> q;

int main(){
	scanf("%d", &N);
	for (int index = 1; index <= N; index++) {
		scanf("%d %d", &b[index].c, &temp);
		b[index].max = b[index].c;
		while (temp > 0) {
			v[temp].push_back(index);
			ind[index]++;
			scanf("%d", &temp);
		}
	}

	for (int index = 1; index <= N; index++) {
		if (ind[index] == 0) {
			q.push(index);
		}
	}

	while (!q.empty()) {
		int position = q.front();
		q.pop();
		if (b[position].max > max_val) {
			max_val = b[position].max;
		}
		for (int index = 0; index < v[position].size(); index++) {
			if (b[v[position][index]].max < b[v[position][index]].c + b[position].max) {
				b[v[position][index]].max = b[v[position][index]].c + b[position].max;
			}
			ind[v[position][index]]--;
			if (ind[v[position][index]] == 0) {
				if (b[ind[v[position][index]]].max > max_val) {
					max_val = b[ind[v[position][index]]].max;
				}
				q.push(v[position][index]);
			}
		}
	}
	for (int index = 1; index <= N; index++) {
		printf("%d\n", b[index].max);
	}
}