[백준/BOJ] 백준 1516번 : 게임 개발

www.acmicpc.net/problem/1516

1516번: 게임 개발

위상정렬을 이용하였고, install_time에 해당 건물의 설치 시간, plus_install_time에 해당 건물 설치 전에 추가되어야 되는 시간, all_install_time에 해당 건물이 완성되기 까지 걸리는 최소 시간을 저장하여 문제를 해결 했다. plus_install_time은 이전에 다수의 건물이 지어져야 될 때 그것들 중 총 완성 시간이 가장 큰 것이므로 그것들 중 총 완성 시간이 가장 큰 것을 저장한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n;
vector<int> install_time(501); //건물 설치 시간
vector<int> plus_install_time(501, 0); //이전에 다수의 건물이 지어져야 될때 그중 더해질 시간중 가장 큰것을 더하므로 가장 큰것을 저장한다
vector<int> all_install_time(501, 0); //해당 건물이 완성되기 까지 걸리는 최소 시간
vector<int> indegree(501, 0);
vector<int> adj[501];

//위상 정렬 알고리즘을 이용
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		int this_time;
		cin >> this_time;
		install_time[i] = this_time;

		while (1)
		{
			int input;
			cin >> input;

			if (input == -1)
				break;

			adj[input].push_back(i);
			indegree[i]++;
		}
	}

	queue<int> q;
	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] == 0)
			q.push(i);
	}

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

		all_install_time[here] += install_time[here]; //해당 건물 설치시간 더하기

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];

			indegree[there]--;
			plus_install_time[there] = max(plus_install_time[there], all_install_time[here]);

			if (indegree[there] == 0)
			{
				all_install_time[there] += plus_install_time[there]; //there 건물 설치 시작 전까지 걸리는 시간 더하기
				q.push(there);
			}
		}
	}

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



	return 0;
}