[BOJ] 백준 1516 게임 개발

문제 링크

www.acmicpc.net/problem/1516

1516번: 게임 개발

 

풀이

백준 1005 - ACM Craft랑 같은 문제입니다.

(어떤 건물을 지을 수 있는 시간 최솟값 + 그 건물을 짓는데 걸리는 시간)이 다음 건물의 d값보다 크면 업데이트해줍니다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

int n, cost[555], indeg[555], d[555];
vvi p;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    p.resize(n + 1);
    queue<int> q;
    for (int i = 1; i < n + 1; i++) {
        cin >> cost[i];
        int x;
        while (cin >> x, x != -1) {
            p[x].push_back(i);
            indeg[i]++;
        }
        if (indeg[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int next: p[now]) {
            d[next] = max(d[next], d[now] + cost[now]);
            if (--indeg[next] == 0) {
                q.push(next);
            }
        }
    }
    for (int i = 1; i < n + 1; i++) {
        cout << d[i] + cost[i] << '\n';
    }
}