Gidhub BE Developer

[BOJ] 게임 개발

2018-01-30
goodGid

Problem

Problem URL : 게임 개발

Code

``````
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

vector<vector<int>> v;
int cost[501];
int idg[501]; // idg is indegree
int cost_dp[501];
int main(){
int n;
cin >> n;
v.resize(n+1);

for(int i=1; i<=n; i++){
int value;
cin >> value;
cost[i] = value;
while (1) {
int a;
scanf("%d",&a);
if( a == -1 ) break;
v[a].push_back(i);
idg[i] ++;
}
}

queue<int> q;
for(int i=1; i<=n; i++){
if( idg[i] == 0){
q.push(i);
cost_dp[i] = cost[i];
}
}

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

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

if( cost_dp[next] < cost_dp[top] + cost[next])
cost_dp[next] = cost_dp[top] + cost[next];

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

for(int i=1; i<=n; i++){
printf("%d\n",cost_dp[i]);
}

return 0;
}

``````

Feed Back

• 위상 정렬(topological sort) 관련 문제 !

• 위상 정렬 문제 도가 튼거 같은 느낌이다 ㅎㅂㅎ

Next : Type