백준 1516번: 게임 개발

문제

문제 바로가기> 백준 1516번: 게임 개발

풀이

위상정렬과 다이나믹 프로그래밍을 이용해서 문제를 풀었다. 여러개의 건물을 동시에 지을 수 있으므로 이전에 지어야 하는 건물이 여러개라면 그 중 최대 값이 다음 건물을 짓기 위해 기다려야 하는 시간이 될 것이다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int n, indegree[501]{}, dp[501]{}, times[501]{};
vector<int> edge[501];

void topologySort(){
    queue<int> q;
    for(int i=1; i<=n; i++){
        if(indegree[i]==0) {
            q.push(i);
            dp[i] = times[i];
        }
    }
    while(1){
        if(q.empty()) break;
        int x = q.front(); q.pop();
        for(int i=0; i<edge[x].size(); i++){
            dp[edge[x][i]] = max(dp[edge[x][i]], dp[x]+times[edge[x][i]]);
            indegree[edge[x][i]]--;
            if(indegree[edge[x][i]]==0) q.push(edge[x][i]);
        }
    }
    for(int i=1; i<=n; i++) cout << dp[i] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++){
        int t; cin>>t; times[i] = t;
        while (1){
            int before; cin>>before;
            if(before==-1) break; 
            indegree[i]++;
            edge[before].push_back(i);
        }
    }
    topologySort();
}