[BOJ] 1516 게임 개발

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

1516번: 게임 개발

 

알고리즘: 위상 정렬

 

시간복잡도: O(N^2)

 

 

BOJ 1005 ACM Craft 와 동일한 문제다.

일의 순서가 정해져 있고, 선행되는 일이 완수되어야 뒷 일을 수행할 수 있다는 조건으로

위상 정렬을 떠올릴 수 있다.

 

// 1516 게임 개발

#include<iostream>
#include<vector>
#include<queue>
#define MAX(a,b) (((a)>(b))?(a):(b))
using namespace std;
int N, h;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	
	vector<int> D(N);	// Delay
	vector<int> p(N, 0);	// # of parents
	vector<int> s[N];	// son nodes
	vector<int> Tt(N, 0);	// Time Table
	queue<int> Q;
	
	for (int i = 0; i < N; i++)
	{
		cin >> D[i];
		while(1)
		{
			cin >> h;
			if (h == -1) break;
			p[i]++;
			s[h-1].push_back(i);
		}
		if (!p[i])
		{
			Tt[i] = D[i];
			Q.push(i);
		}
	}
	
	while(!Q.empty())
	{
		h = Q.front();
		Q.pop();
		
		for (int i : s[h])
		{
			p[i]--;
			Tt[i] = MAX(Tt[i], Tt[h]+D[i]);
			if (!p[i])
				Q.push(i);
		}
	}
	
	for (int i : Tt)
		cout << i << "\n";
	return 0;
}