[백준/BOJ] 1516 게임 개발

문제 : 1516 게임 개발

1516번: 게임 개발

건물을 짓는데 걸리는 시간과 그 건물을 짓기 전에

먼저 지어져야 하는 건물의 번호가 주어졌을 때,

그 건물을 짓는데 걸리는 최소 시간을 출력하는 문제이다.

위상 정렬을 사용해 현재 지을 수 있는 건물부터 순차적으로 지으면서

그 건물을 짓는 시간을 구해주면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, build[505], chk[505], ans[505];
vector<ll> arr[505];
void TopologySort(){
    queue<ll> q;
    for (int i=1;i<=N;i++){
        if (chk[i]==0)
            q.push(i);
    }
    for (int i=1;i<=N;i++){
        ll x=q.front();
        q.pop();
        ans[x]+=build[x];
        for (int j=0;j<arr[x].size();j++){
            ll dx=arr[x][j];
            ans[dx]=max(ans[x],ans[dx]);
            if (--chk[dx]==0)
                q.push(dx);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i=1;i<=N;i++){
        cin >> build[i];
        while (1){
            ll a;
            cin >> a;
            if (a==-1)
                break;
            arr[a].push_back(i);
            chk[i]++;
        }
    }
    TopologySort();
    for (int i=1;i<=N;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}