게임 개발 (feat. 백준, 1516번)

게임 개발
https://www.acmicpc.net/problem/1516

1516번: 게임 개발

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> arr[501];
int check[501]{0};
int time[501]{0}, ans[501]{0};
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N;
    cin >> N;
    for(register int n = 1, b; n <= N; ++n){
        cin >> time[n], ans[n] = time[n];
        while(1){
            cin >> b;
            if(b == -1)
                break;
            arr[b].push_back(n);
            ++check[n];   
        }
    }
    priority_queue<int, vector<int>, greater<int>> q;
    for(register int n = 1; n <= N; ++n)
        if(!check[n])
            q.push(n);
    while(!q.empty()){
        auto pos = q.top(); q.pop();
        for(auto& v : arr[pos]){
            if(ans[pos] + time[v] > ans[v])
                ans[v] = ans[pos] + time[v];
            if(--check[v] == 0)
                q.push(v);
        }
    }
    for(register int n = 1; n <= N; ++n)
        cout << ans[n] << '\n';
	return 0;
}
// *&)*@*

 

반응형

위상정렬을 특성을 활용하여 풀이할 수 있습니다.

문제의 내용이 다르더라도 위상정렬은 우선순위 큐를 활용하는 풀이의 특징이 동일하므로 연습이 필요합니다.