[백준] 1516번 게임개발 [C++]

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

1516번: 게임 개발

---

문제

 

---

접근 방식

위상 정렬을 통해, 건물을 순서대로 지으면 된다.

순서대로 짓는 과정에서, 건물을 지을 때 의 최소 시간을 구하는 방식은 다이나믹 프로그래밍 기법을 사용하면 되는데

현재 건물까지 짓는 시간 = max(선행 건물 중 가장 오래 걸리는 건물) + 현재 건물을 짓는데 걸리는 시간

이라는 식이 세워지게 된다.

 

---

#include <iostream>
#include <vector>
#include<queue>
using namespace std;
int incounter[501];
vector<int> v[501]; //해당 건물이 선행 건물인 건물들
vector<int> outv[501];//해당건물의 선행 건물들
bool flag[501];
int arr[501];
int n;
int dp[501];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int t,x;
		cin >>t>> x;
		arr[i] = t;
		while (x != -1) {
			incounter[i]++;
			v[x].push_back(i);
			outv[i].push_back(x);
			cin >> x;
		}
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (incounter[i] == 0) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int x = q.front();
		int maxi = 0;
		q.pop();
		for (int i = 0; i < outv[x].size(); i++) {
			maxi = max(maxi, dp[outv[x][i]]);
		}
		dp[x] = maxi + arr[x];
		for (int i = 0; i < v[x].size(); i++) {
			incounter [v[x][i]] --;
			if (incounter[v[x][i]] == 0)q.push(v[x][i]);
		}
	}
	for (int i = 1; i <= n; i++)cout << dp[i] << '\n';
}

---

위상 정렬에 대해 공부하기 전에 한번 도전했을 때는 어떻게 해야할지 감을 못 잡았는데, 위상정렬을 알고 푸니까 정말 쉽게 풀린 문제였다.