백준) 1516 게임 개발

게임 개발

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

테크트리를 타고 모든 건물을 지어야 한다. 모든 건물을 짓는데 시간이 얼마나 들까?

생각해야 할 점은 건물들이 동시에 지어질 수 있다는 점이다.

예를 들어 현재 배럭과 벙커를 지을 수 있다면, 배럭을 짓는데 시간이 더 오래 걸리므로 배럭 건설시간이 정답이 된다.

큐는 현재 지을 수 있는 건물(진입차수가 0이 된 노드)을 담고 있으므로,

큐를 건설시간이 작은 순으로 정렬되는 우선순위 큐로 바꾼다면, 맨 뒤에 있는 배럭이 정답에 반영될 것이다.

다르게 말하자면,

a->b (10)// c->b (20)라는 테크트리에 대해, 

b를 짓기 위해선 a와 c를 둘 다 지어야 하지만, b를 짓기 위한 준비 시간은 c만 포함된다.

따라서 b로 진입하는 두 간선 중 가벼운 a가 먼저 지어지면서 간선이 없어지지만, 무거운 c간선이 남아있으므로

정답에 반영되지 않는다.

다음으로 c간선이 없어지면서 b를 지을 수 있게되었다. 이제 가장 무거웠던 c간선의 20초가 정답에 들어간다.

#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
struct build {
    int num, time;
};
bool operator <(const build& a, const build& b) {
    if (a.time != b.time)
        return a.time > b.time;
    return a.num > b.num;
}
build buildings[501];
 
int n, a, b, c;
int in[501];
 
int main() {
    scanf("%d", &n);
    vector<vector<int>> vec(n + 1);
 
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a);
        buildings[i].time = a;
 
        while (1) {
            scanf("%d", &a);
            if (a == -1)
                break;
 
            vec[a].push_back(i);
            in[i]++;
        }
    }
 
    priority_queue<build> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i])
            q.push({i,buildings[i].time});
    }
 
    while (!q.empty()) {
        int cur = q.top().num;
        q.pop();
 
        for (auto next : vec[cur]) {
            in[next]--;
            if (!in[next]) {
                buildings[next].time += buildings[cur].time;
                q.push({next, buildings[next].time});
            }    
        }
    }
 
    for (int i = 1; i <= n; ++i)
        printf("%d\n", buildings[i].time);
 
    return 0;
}