[BOJ] 1516 : 게임 개발 - travelbeeee

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

---

위상 정렬

● 건물을 동시에 지을 수 있으므로, 각 건물별로 필요한 시간은 그래프 경로 중 가장 긴 경로가 된다.

● ans[i] := 건물 순서를 고려해 i 번 째 건물을 짓는데 필요한 최대 시간.

● time[i] := 단순히 i번 째 건물만 짓는데 걸리는 시간.

위상 정렬을 이용해 inDegree가 0인 노드부터 탐색을 시작해, 현재 탐색중인 노드에서 연결된 노드들의 ans[i] 를 계속 갱신을 해주면 된다. 예시를 통해 다뤄보겠다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, M, inDegree[501] = {}, time[501] = {}, ans[501] = {};
	vector<int> graph[501] = {};
	stack<int> s;

	cin >> N;
	for (int i = 1, x; i <= N; i++) {
		cin >> time[i];
		while(1){
			cin >> x;
			if (x == -1)
				break;
			graph[x].push_back(i);
			inDegree[i]++;
		}
	}

	for (int i = 1; i <= N; i++)
		if (inDegree[i] == 0){
			s.push(i);
			ans[i] = time[i];
		}

	while (!s.empty()) {
		int cur = s.top();
		s.pop();

		for (int i = 0; i < graph[cur].size(); i++) {
			inDegree[graph[cur][i]]--;
			ans[graph[cur][i]] = max(ans[graph[cur][i]], ans[cur] + time[graph[cur][i]]);
			if (inDegree[graph[cur][i]] == 0) {
				s.push(graph[cur][i]);
			}
		}
	}

	for (int i = 1; i <= N; i++)
		cout << ans[i] << '\n';

	return 0;
}

---