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

문제 링크: https://www.acmicpc.net/problem/1516

 

위상정렬 문제입니다. 기본형 문제입니다.

Indegree를 사용한 위상정렬로 풀어봤습니다.

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;


vector<int> adj[500];	// idx
vector<int> indegree;
vector<int> cost;		// 건설시간
vector<int> cache;		// 각 건물당 최소 건설시간
int n;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> n;

	cost.resize(n);
	cache.resize(n);
	indegree.resize(n);


	for (int i = 0; i < n; ++i) {
		cin >> cost[i];
		cache[i] = cost[i];

		int in;
		while (cin >> in) {
			if (in == -1) break;
			--in;

			adj[in].emplace_back(i);
			++indegree[i];
		}
	}

	queue<int> q;	// indegree == 0인거 저장
	for (int i = 0; i < n; ++i) {
		if (indegree[i] == 0) {
			cache[i] = cost[i];
			q.push(i);
		}
	}

	while (!q.empty()) {
		int current = q.front();
		q.pop();

		for (auto next : adj[current]) {
			cache[next] = max(cache[next], cache[current] + cost[next]);
			if (--indegree[next] == 0)
				q.push(next);
		}
	}

	for (int i = 0; i < n; ++i)
		cout << cache[i] << '\n';
	
	return 0;
}