백준 1516 : 게임 개발

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

순차적으로 진행해야 하는 DAG그래프를 다룰 때 위상정렬을 생각할 수 있다.

건물을 짓는데 필요한 건설시간과 건물을 짓기 이전에 걸리는 건설시간을 분리했다.

위상정렬을 할때 건물을 짓기 이전에 걸리는 시간이 최대여야 하기 때문이다.

예를들어 a를 짓기위해 b 와 c가 지어져야 하는데 b는 짓는데 총합 10초이고 c는 총합 20초라면

a건설을 시작할 수 있는 시기는 c가 완료된 20초에나 가능한 것이다. 이를 유의해서

건물짓기 이전에 걸리는 건설시간을 MAX로 갱신시켜주어야 한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include <iostream> #include <vector> #include <queue> #define MAX 501 using namespace std; struct Building{ int buildTime, indegree, postTime = 0; vector<int> next; }; Building building[MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for(int i = 1; i <= n; i++){ cin >> building[i].buildTime; while(true){ int post; cin >> post; if(post == -1) break; building[post].next.push_back(i); building[i].indegree++; } } queue<int> q; for(int i = 1; i <= n; i++){ if(building[i].indegree == 0){ q.push(i); } } while(!q.empty()){ int curIdx = q.front(); q.pop(); for(int nIdx : building[curIdx].next){ if(building[nIdx].postTime < building[curIdx].buildTime + building[curIdx].postTime){ building[nIdx].postTime = building[curIdx].buildTime + building[curIdx].postTime; } if(--building[nIdx].indegree == 0){ q.push(nIdx); } } } for(int i = 1; i <= n; i++){ cout << building[i].buildTime+building[i].postTime << '\n'; } return 0; }