[BOJ/C++] 1516 게임 개발

"어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다" 라는 문장에서

노드 순서를 정렬하는 위상 정렬을 사용하는 문제임을 알 수 있습니다.

중요한 점은 다음 건물에 저장된 시간, 현재 건물에 저장된 시간 + 다음 건물의 생산 시간의 최댓값으로 업데이트 해야합니다.

result[next] = max(result[next], result[now] + buildTime[now]);

건물 A, B, C가 각각 1, 2, 3의 생산 시간을 가지고 있고 C는 A와 B를 먼저 지어야할 때

각각 A(1+3), B(2+3)으로 C 건물의 생산 시간을 업데이트할 수 있습니다.

이 때, 더 오래걸리는 B 건물 기준으로 업데이트 해야합니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>

using namespace std;

using int32 = long;
using int64 = long long;

static vector<vector<int>> G;
static vector<int> inDegree;
static vector<int> buildTime;
static vector<int> result;


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

    int N;
    cin >> N;

    G.resize(N+1);
    inDegree.resize(N+1);
    buildTime.resize(N+1);
    result.resize(N+1);

    for(int i=1; i<=N; i++)
    {
        cin >> buildTime[i];

        while (true)
        {
            int temp;
            cin >> temp;

            if (temp == -1)
                break;

            G[temp].push_back(i);
            inDegree[i]++;
        }
    }

    queue<int> q;

    for(int i=0; i<=N; i++)
    {
        if (inDegree[i] == 0)
            q.push(i);
    }

    while(!q.empty())
    {
        int now = q.front();
        q.pop();

        for(int next : G[now])
        {
            inDegree[next]--;
            
            result[next] = max(result[next], result[now] + buildTime[now]);

            if (inDegree[next] == 0)
                q.push(next);
        }
    }

    for (int i = 1; i <= N; i++)
        cout << result[i] + buildTime[i] << '\n';


    return 0;
}