[baekjoon 1516] 게임 개발 (위상정렬, DP) (C++)

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

1516번: 게임 개발

입력으로 각 건물을 짓는데 걸리는 시간과, 이 건물을 짓기 위해서 선행되어야 하는 건물의 번호가 주어진다.

즉, 건물을 짓는 순서를 그래프로 나타내면 DAG(Directed Acyclic Graph) - 사이클을 갖지 않는 단방향 그래프가 되고, 이를 통해 노드 간 고유 순서를 위배하지 않으면서 정렬하는 위상 정렬을 이용할 수 있다.

 

위상 정렬의 방법은 1. 스택을 이용하는 방법과 2. 큐를 이용하는 방법이 있고 이 문제에서 나는 큐를 이용했다.

 

1. 스택을 이용하는 경우

방문하지 않은 노드에 DFS를 진행하면서 만약 노드가 더 이상 방문할 노드가 없다면 스택에 넣어준다.

그렇게 되면 순서가 가장 느린 값(다른 노드가 모두 선행되고 난 마지막 노드) 순서로 스택에 차곡차곡 쌓인다.

재귀적으로 스택에 쌓이게 되고, 마지막으로 그래프에서 가장 첫 순서인 노드가 자신과 연결된 모든 노드를 dfs로 방문 후에 스택에 들어간다.

 

따라서 스택 순서로 다시 꺼내면 위상 순서대로 출력이 가능하다.

 

2. 큐를 이용한 경우

큐를 이용하는 경우 진입 차수(inDegree) 기준으로 진행해준다. 진입 차수라는 것은 결국 단방향 그래프에서 해당 노드로 ->가 들어오는 경우이며, 가장 첫 순서인 노드는 자신을 가리키는 진입 차수는 0이 된다. (첫 순서이므로 선행 노드가 없음)

 

따라서, 진입 차수가 0인 노드부터 큐에 넣어주고 노드 개수만큼 반복문을 돌며 큐에서 노드를 하나씩 빼주며 저장한다.

큐에서 나온 노드는 진입 차수가 0인 노드이며 그 노드가 가리키고 있는 노드들을 탐색하면서 다음 진입 차수가 0인 노드를 큐에 넣어주며 반복해준다. (0인 노드(x)가 연결된 노드(x')들을 확인하면서 x-x'의 진입 관계는 지워준다.)

 

이 경우, 저장한 순서대로 출력하면 그것이 위상 순서이다.

 

이 문제에서는 큐를 이용해서 진행하는 경우에 건물을 짓는 비용을 추가해주었다.

한 건물에 여러 선행 건물이 있는 경우가 있는데 건물을 동시에 짓는 경우가 있으므로 그 비용들 중 가장 최대 비용을 더해줘야 한다.

그림이 필요한데 그림이 없어서 밑의 코드와 주석으로 이해해보자..

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <queue>

	using namespace std;

	int N, t, need, timer[501], result[501], inDegree[501];
	vector<int> v[501];
	queue<int> q;

	void topologicalSort() {
		for (int i = 1; i <= N; i++) {
			if (inDegree[i] == 0) { // 진입 차수 0인 노드 넣어주기
				q.push(i);
			}
		}

		for (int i = 1; i <= N; i++) {
			int now = q.front();
			q.pop();
			result[now] += timer[now]; // 1)  2)에서 진행된 갱신된 최대비용 + 자신 건물 짓는 비용
			for (int i = 0; i < v[now].size(); i++) {
				int next = v[now][i];
				if (result[next] != 0) { // 이미 방문한 경우 dp로 갱신해준다.
					result[next] = max(result[next], result[now]); // 2) 다음 노드들은 앞에 연결된 노드들 중 최대 비용으로 갱신
				}
				else // 방문한 적 없으면 첫 방문 비용으로 저장
					result[next]  = result[now];

				inDegree[next]--;
				if (inDegree[next] == 0) {
					q.push(next);
				}
			}
		}
	}

	int main() {
		ios::sync_with_stdio(false);
		cin.tie(0);
		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> t;
			timer[i] = t;
			while (1) {
				cin >> need;
				if (need == -1)
					break;
				v[need].push_back(i); // 선행 건물의 원소로 들어간다. v[1] =  2 : 2번 짓는데 1번이 선행 
				inDegree[i]++; // 진입차수 더해주기
			}
		}

		topologicalSort();

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