[C++][백준 1516] 게임 개발

[문제]

1516번: 게임 개발 (acmicpc.net)

1516번: 게임 개발

[문제 풀이]

백준 1005번(ACM CRAFT) 문제와 90% 이상 흡사하다고 보면 된다.

1 -> 2 / 2 -> 4 / 3 -> 4 로 향하는 그래프가 있을때 4번의 완성이 되는 가장 짧은 시간은 1,2,3번이 완성되는 마지막 시간이고 이것은 1,2,3번의 max타임이라고 보면 된다.

[회고]

max를 넣어두는 곳을 if문 안에 뒀는데 테케가 맞는걸 보고 생각없이 제출했다. 테케가 생각 못한 경우로 맞을 수 있으니 한번 다시 확인해보자.

[코드]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define endl "\n"

using namespace std;

vector<int> building[501];
vector<int> result;
int cost[501];
int cost2[501];
int adj[501];
int n;

void topological(){
    queue<int> q;

    for(int i = 0;i<=n;i++){
        cost2[i] = cost[i];
    }
    
    for(int i = 1;i<=n;i++){
        if(adj[i] == 0){
            q.push(i);
        }
    }

    while(q.size() > 0){
        int cur = q.front();
        q.pop();

        for(int i = 0;i<building[cur].size();i++){
            int next = building[cur][i];
            adj[next]--;
            if(adj[next] == 0){
                q.push(next);
            }
            cost2[next] = max(cost2[next],cost2[cur] + cost[next]);
        }
    }

    for(int i = 1;i<=n;i++){
        cout<<cost2[i]<<endl;
    }

    return;
}

int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>cost[i];
        int b;
        while(cin>>b){
            if(b == -1){
                break;
            }
            adj[i]++;
            building[b].push_back(i);
        }
    }

    topological();

    return 0;
}