백준 1516 게임 개발 (C++)

1516번: 게임 개발

위상 정렬을 이용한 문제이다. 모든 건물의 최소 시간을 구하면 된다. 기존 위상 정렬 방식을 그대로 사용하였다. 입력을 받아온 값들을 bfs를 통해 값들을 구해나가 출력하였다.
기존에 풀었던 백준 1005 ACM Craft (C++)와 굉장히 유사한 문제였다. 위상 정렬 문제를 많이 풀어 봐야겠다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N;
vector<int> v[501];
int cost[501];
int inDegree[501];
int dp[501];

void solution(){
    queue<int> q;

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

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

        q.pop();

        for (int i = 0; i < v[cur].size(); i++) {
            int next = v[cur][i];

            inDegree[next]--;
            dp[next] = max(dp[next], dp[cur] + cost[next]);

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

    for (int i = 1; i <= N; i++) {
        cout << dp[i] << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

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

        for (int j = 1; j < N; j++) {
            int a;
            cin >> a;

            if (a == -1) break;

            v[a].push_back(i);
            inDegree[i]++;
        }
    }

    solution();

    return 0;
}