(C++) - 백준(BOJ) 1516번 : 게임개발

https://www.acmicpc.net/problem/1516

1516번: 게임 개발

위상정렬문제였습니다. 

 

풀이방법

  짓는데 오래걸리는 순으로 pq에 넣어 꺼내 확인하면서 진입차수를 줄여가는 방식으로 구현합니다. 진입차수가 0이라면 현재정점 x가 가장 최적으로 지을 수 있는 건물이므로 x의 시간을 next정점의 시간에 더해서 갱신해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, ind[501];


struct Edge {int v, w; };
vector <Edge> building(501);
vector <int> graph[501];

bool operator < (const Edge &a, const Edge &b){
    if(a.w != b.w) return a.w > b.w; 
    return a.v > b.v;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x, cost;
        cin >> cost;
        building[i].w = cost;

        while(1){
            cin >> x;
            if(x == -1) break;
            graph[x].push_back(i);
            ind[i]++;
        }
    }
    priority_queue <Edge> pq;
    for(int i = 1; i <= n; i++){
        if(!ind[i]) pq.push({i,building[i].w});
    }

    while(!pq.empty()){
        int x = pq.top().v;
        int cost = pq.top().w;
        pq.pop();
        for(auto next : graph[x]){
            ind[next]--;
            if(!ind[next]){
                building[next].w += building[x].w;
                pq.push({next,building[next].w});
            }
        }
    }
    
    for(int i = 1; i <= n; i++) cout << building[i].w << '\n';
}