[백준 1516번] 게임 개발 (C++)

문제링크 : https://www.acmicpc.net/problem/1516

1516번: 게임 개발

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, num;
vector<int>v[501];
int inDegree[501], dp[501], arr[501];
queue<int>q;

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

    cin >> N;
    for(int i=1; i<=N; i++)
    {   
        cin >> arr[i];
        while(1)
        {
            cin >> num;
            if(num==-1) break;
            v[num].push_back(i);
            inDegree[i]++;
        }
    }

    for(int i=1; i<=N; i++)
    {
        if(inDegree[i]==0) 
        {
            q.push(i);
            dp[i]=arr[i]; //초기화
        }
    }

    while(!q.empty())
    {
        int cur = q.front(); q.pop();
        for(int i=0; i<v[cur].size(); i++)
        {
            int next = v[cur][i];
            dp[next] = max(dp[next], dp[cur]+arr[next]); //점화식
            if(--inDegree[next]==0) q.push(next);
        }

    }

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

 

위상정렬 알고리즘을 사용하는 [백준 1005번] ACM Craft과 거의 동일한 문제이다.

따라서 아래와 같이 해당 문제에 대한 링크를 첨부하는 것으로 풀이를 대신하였다.

 

ACM Craft 문제 링크 : https://blob-thinking.tistory.com/289

[백준 1005번] ACM Craft (C++)