[c++] 위상정렬 백준-게임개발

1. 문제 

 

2. 입 출력

 

1. 생각해볼 것

처음엔 위상정렬을 한 후 누적합을 구하는 문제인 줄 알았다.. 

하지만 하나 놓치고 있었던 것이 있었다. 

건물이 동시 다발적으로 건설 될 수 있었다는 것이다. 

 

즉, 

4
1	4	3	2	-1
2	4	-1
1	4	-1
1	-1

위와 같은 입력이 있을 때 누적합으로 구한다면 

1번 건물은 4 3 2가 선행되어야 하므로 dist[4]+dist[3]+dist[2]+dist[1] = 5가 되어야한다. 

2번 건물은 4가 선행되어야 하므로 dist[2] + dist[4] = 3

3번 건물은 4가 선행되어야하므로 dist[3] + dist[4] = 2

4번 건물은 선행되어야하는 건물이 없으므로 그대로 dist[1] = 1이 된다. 

 

그러나 답은 

 

4 3 2 1이 된다. 왜일까?

 

위의 그래프를 그림으로 나타내면 위와 같다. 

이 문제의 해법은 기본적으로 위상정렬을 기본으로 하므로 자신에게 향하는 화살표가 없는 4부터 시작한다. 

4에서 향하는 모든 화살표를 제거하면 2 와 3 노드로 향하는 화살표가 존재하지 않게 되는데 따라서

2는 dist[2]+dist[4]

3은 dist[3]+dist[4] 가 된다. 

하지만 2 와 3은 같은 레벨에서 inDegree(자신에게 향하는 화살표의 수)가 0이 되므로 둘의 순서는 변경될 수 있다. 

또한 건물은 동시에 지어질 수 있으므로 2와 3은 동시에 지어질 수 있다. 따라서 1번 건물을 지을 때 들어가는 최소 비용은

 

4번 건물을 짓고 2번 건물을 짓고 3번 건물을 짓고 1번 건물을 짓는 것과 

4번 건물을 짓고 3번 건물을 짓고 2번 건물을 짓고 1번 건물을 짓는 것 이 아니라

 

4번 건물을 짓고 2번 , 3번 건물 중 더 큰 비용이 드는 건물 + 1번 건물을 짓는 것이 되는 것이다. 

 

따라서 코드는 다음과 같다. 

 

위상정렬을 기반으로 한다. 

 

3. 코드

#pragma warning (disable: 4996)
/*
	백준 - 게임개발
	위상 정렬 문제인 거 같다. 
	위상 정렬 문제에서는 inDegree배열이 중요하다. 

	하나의 노드를 탐색하면서 inDegree를 없앤다. 
	모두 없앤 후 탐색하며 inDegree가 0인 노드들은 누적합 배열을 통해 구해준다. 
*/
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 502
using namespace std;
int N;
vector <int> v[MAX]; // 인접 행렬
int dist[MAX];
int inDegree[MAX];
int result[MAX];
void input() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		int tmp = 0;
		for (int j = 0; j <= N; j++) {
			if (j == 0) {
				scanf("%d", &tmp);
				dist[i] = tmp;
			}
			else {
				scanf("%d", &tmp);
				if (tmp == -1) break;
				v[tmp].push_back(i);
				inDegree[i]++;
			}
		}
	}

	/*for (int i = 1; i <= N; i++) {
		printf("%d ", dist[i]);
	}
	printf("\n");*/
}
void topologySort() {
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0) { 
			q.push(i); 
			result[i] = dist[i];
		} // 만약 inDegree가 0인 것이 있다면 q에 넣어준다.
	}
	if (q.empty()) return;

	while (q.size()) {
		int x = q.front(); q.pop();
		for (int a : v[x]) {
			inDegree[a]--;
			result[a] = max(result[a], result[x] + dist[a]); // 더 큰 값을 넣어준다.
			if (inDegree[a] == 0) {
				q.push(a); // q에 집어넣는다.
			}
		}
	}
}
int main() {
	input();
	topologySort();

	for (int i = 1; i <= N; i++) {
		printf("%d\n", result[i]);
	}
	
	return 0;
}