백준 1516번 - 게임 개발 (C++, 위상정렬, 다이나믹 프로그래밍)

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

 

다시풀어본 위상정렬 + 다이나믹 프로그래밍 문제이다.

문제 분류가 다이나믹 프로그래밍이라 dp라 쓰긴 했는데 솔직히 이게 dp인가 싶다. 그냥 정답을 계속 갱신하는데만 쓰이는데 이게 디피라고 볼 수 있는건가..?

 

 

위상정렬은 순서가 정해진 그래프를 보고 그 순서대로 정렬이 가능한 유용한 알고리즘이다. 그것을 사용해 이 예제를 풀어보자.

선행조건이 없는 1번과 7번 건물이 먼저 지어질 것이다. 3번의 경우 1번을 짓는데 100의 시간, 7번이 200, 6번이 300 이라 가정하면 3번을 짓는데 드는 시간은 6,7번을 지어야하는 500의 시간이다. 

 

그리고 3은 1번에서 도착할 경우와 6번에서 도착할 경우를 비교해야한다. 즉,

 

F(3) = compare( F(1) , F(6) ) 

 

1에서 먼저 3에 접근했다면 F(3) 는 100의 시간이 소요되는 것으로 기록이 된다. 그리고 이후 6번에서 3으로 접근했으면 이전에 저장해둔 100과 500을 비교해 더 큰 수를 담는다.

 

왜냐하면 결국 더 큰 시간을 소모하는 것이 이 건물을 지을 수 있는 최소시간이기 때문이다. 이것은 위상정렬을 통해 증명된다.

그래서 이것을 점화식으로 새우면

 

 

마지막으로 코드로 나타내면 다음과 같다.

 

/*

1 -> 10초
2 -> 10초 / 1번 건물
3 -> 4초 / 1번 건물
4 -> 4초 / 1번, 3번 건물
5 -> 3초 / 3번 건물

1 : 10
2 : 20
3 : 14
4 : 18
5 : 17

*/

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

vector<int> build[501];
vector<int> Cost(501, -1);
vector<int> degree(501, 0);
vector<int> answer(501, 0);

int N;

void bfs(){
	queue<int> nodes;

	for(int i = 1; i <= N; i++){
		if(degree[i] == 0){ // 선행 조건이 없음
			nodes.push(i);
			answer[i] = Cost[i];
		}
	}

	while(!nodes.empty()){
		int node = nodes.front();
		nodes.pop();

		for(int i = 0; i < build[node].size(); i++){
			int nextNode = build[node][i];
			degree[nextNode]--;
			answer[nextNode] = max(answer[nextNode], Cost[nextNode] + answer[node]);

			if(degree[nextNode] == 0){
				nodes.push(nextNode);
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	for(int i = 1; i <= N; i++){
		int tmp = 0;
		int cost; cin >> cost;

		Cost[i] = cost;

		while(true){
			cin >> tmp;

			if(tmp == -1) break;
			build[tmp].push_back(i);
			degree[i]++;
		}
	}

	bfs();

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