[BOJ] 1516. 게임 개발 : https://www.acmicpc.net/problem/1516. 위상정렬

게임 개발.cc

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

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<vector<int>> adj(n);
	vector<int> cost(n);

	// input 
	int c, tmp;
	for (int i = 0; i < n; i++) {
		cin >> c >> tmp;
		cost[i] = c;
		while (tmp != -1) {
			adj[i].push_back(tmp - 1);
			cin >> tmp;
		}
	}

	// topologic sort
	queue<int> q;
	vector<int> ans(n, 0);
	int sum = 0;

	// set q
	for (int i = 0; i < n; i++) {
		if (adj[i].empty()) {
			q.push(i);
			ans[i] = cost[i];
		}
	}

	while (!q.empty()) {

		int now = q.front();
		int nCost = ans[now];
		q.pop();

		for (int i = 0; i < n; i++) {
			for (vector<int>::iterator it = adj[i].begin(); it != adj[i].end(); it++) {
				if (*it == now) {
					adj[i].erase(it); // delete 
					ans[i] = max(ans[i], cost[i] + nCost); // update ans
					if (adj[i].size() == 0) q.push(i);
					break;
				}
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
		cout << ans[i] << endl;
	}

	return 0;
}