백준 1516 게임 개발

A를 짓고 B를 지어야 한다면

A->B와 같이 모델링 한 뒤,

위상정렬을 수행하면서 시간을 계산한다.

여기서 defaultTime은 기본 건설 시간,

addTime은 건설을 위해 선행으로 지어야 하는 건물들을 건설하기 위해 기다리는 시간이다.

그래프가 다음과 같다고 하자

A->E

F->C

B->C->D->E

이럴 경우 E를 짓는 시간은

E를 짓는 기본 시간(defaultTime[E])

+

E의 선행 건물들의 건설 시간중 최대값(addTime[E])이다.

addTime[E]는 A의 총 건설 시간과 D의 총 건설시간의 최대값이고, A의 총 건설 시간은 defaultTime[A]이다.

한편 D의 총 건설 시간은 C의 총 건설 시간 + D의 기본 건설시간이고,

이때 C의 총 건설 시간은 위상정렬을 하면서 C에 접근했을때 (defaultTime[C] + addTime[C])로써 미리 계산되어 있는 값이다.

(왜냐하면, 위상정렬을 수행하면서 F와 B에 이미 접근을 했을 태고, 그로써 F와 B는 C의 addTime에 이미 영향을 끼쳤을 것이기 때문)

따라서 E의 추가 건설시간 (addTime[E])은 max( (defaultTime[A] + addTime[A]), (defaultTime[E] + addTime[E]) ) 이고,

E의 총 건설 시간은 defaultTime[E] + addTime[E]가 된다.

한편, 노드 X가 노드 Y와 연결되어 있어서 

X에서 위상정렬을 하면서 Y를 위상정렬 큐에 넣었다면,

다음 루프로 가기 전 Y의 addTime을 갱신한다(지금 저장되어있는 addTime[Y]을 max( addTime[Y], (defaultTime[X] + addTime[X]) ) 로 갱신)

//deque.tistory.com

#define _CRT_SECURE_NO_WARNINGS

#include <iostream> 
#include <vector> 
#include <queue> 
#include <map>
#include <fstream> 
#include <string> 
#include <algorithm>

using namespace std;

int indegree[502];
int defaultTime[502];
int addTime[502];
int N;
vector<int> adj[502];

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &defaultTime[i]);

		int input;
		while (true) {
			scanf("%d", &input);
			if (input == -1) break;

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

	queue<int> topoloQ;

	for (int i = 1; i < N; i++) {
		if (indegree[i] == 0) {
			topoloQ.push(i);
		}
	}

	while (!topoloQ.empty()) {
		int size = topoloQ.size();
		for (int loop = 0; loop < size; loop++) {
			int now = topoloQ.front();
			topoloQ.pop();
			indegree[now]--;
			for (int next : adj[now]) {
				indegree[next]--;
				if (indegree[next] == 0) {
					topoloQ.push(next);
				}
				int prevConstructTime = defaultTime[now] + addTime[now];
				if (prevConstructTime > addTime[next]) {
					addTime[next] = prevConstructTime;
				}
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		printf("%d\n", defaultTime[i] + addTime[i]);
	}

	return 0;
}