게임 개발

백준 1516번: 게임 개발

아이디어

위상정렬 후 순서대로 방문하면서 각 건물을 짓는데 필요한 시간을 기록한다. 이전 건물까지 짓는데 소요된 시간 + 현재 건물을 짓는데 필요한 시간 vs 현재 건물까지 짓는데 소요된 시간을 비교하여 더 큰 값으로 교체한다.
어떤 건물 v의 가장 빠른 건설완료시간은, v로 들어오는 모든 정점들 중 가장 늦은 건설완료시간이 결정하기 때문.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 501;
int N;
vector<vector<int>> adj;
int cost[MAX];
bool visited[MAX];
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int next : adj[v]) {
        if (!visited[next]) dfs(next);
    }
    ans.push_back(v);
}

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

    cin >> N;
    adj = vector<vector<int>>(N+1);
    for (int i = 1; i < N+1; i++) {
        cin >> cost[i];
        int x;
        while (1) {
            cin >> x;
            if (x == -1) break;
            adj[x].push_back(i);
        }
    }

    for (int i = 1; i < N+1; i++) {
        if (!visited[i]) dfs(i);
    }

    int tc[N+1];
    for (int i = 1; i < N+1; i++) {
        tc[i] = cost[i];
    }
    for (auto x = ans.rbegin(); x != ans.rend(); x++) {
        for (int n : adj[*x]) {
            tc[n] = max(tc[n], cost[n]+tc[*x]);
        }
    }
    for (int i = 1; i < N+1; i++) {
        cout << tc[i] << '\n';
    }

    return 0;
}

여담

스택에 넣고 다시 뽑아서 순서대로 만들바에 걍 벡터에 넣고 rbegin으로 순회