백준 1516 게임 개발

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

1516번: 게임 개발

 

위상정렬 문제다.

 

차이가 있다면 '시간'이라는 변수가 추가된 것!

 

보통은 'C건물이 완성되려면 A건물과 B건물이 완성되어야 합니다' 라는 문제조건에 따라 

 

inedge의 개수만 세면 되는데 이 문제는 '시간'이 기준이어서 A건물과 B건물이 완성되는 시간 모두를 고려하는 게 아니라

 

둘 중 더 늦게 완성되는 건물의 완성 시간을 기준으로 잡아야 한다.

 

즉 Queue가 아니라 priority Queue를 써야 한다.

/* 게임 개발 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, in[500 + 1], time[500 + 1], precedence[500 + 1];
bool is_visit[500 + 1];
vector<int> building[500 + 1];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 1; i <=N; i++) {
		cin >> time[i];
		while (true) {
			int temp;
			cin >> temp;

			if (temp == -1) {
				break;
			}
			
			building[temp].push_back(i);
			in[i]++;
		}
	}

	priority_queue<pair<int,int>> history;
	for (int i = 1; i <= N; i++) {
		if (in[i] == 0) {
			is_visit[i] = true;
			history.push({ time[i], i });
		}
	}
	
	while (!history.empty()) {	
		int current_building = history.top().second;
		int current_time = history.top().first;
		history.pop();

		for (auto i : building[current_building]) {
			if (is_visit[i]) continue;
			precedence[i] = max(precedence[i], current_time);
			in[i]--;
			if (in[i] == 0){
				is_visit[i] = true;
				time[i] += precedence[i];
				history.push({ time[i], i });
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		cout << time[i] << '\n';
	}
	return 0;
}