[BOJ] 게임개발

[문제]

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

1516번: 게임 개발

[풀이]

 

1516

맞았습니다!!

2400

4

C++14 / 수정

1335

3분 전

 

1) 위상정렬 문제입니다. 

 

2) 건물들의 우선순위가 주어지는데 원래 건물이 지어지는 시간을 잘 저장 해놔야한다.

이건 '질문하기' 에서 찾은 답변인데 딱 이해가는 설명입니다.(누적 시간을 계산하는 과정에서 왜 max 처리를 해야하는지)  

만약 A,B가 끝나는 시간이 다르다면 둘 중 늦게 끝나는 시간 + C를 짓는데 걸리는 시간이 답이 되어야 합니다.

하지만 위 소스 대로라면 A,B중 만약 B가 시간이 더 오래 걸린다고 할 때, B가 먼저 건설된 뒤, A가 건설된다면 C를 짓는데 걸리는 시간은 A+C시간이 됩니다.

따라서 우선순위 큐를 통해 A가 먼저 건설된 뒤, B가 건설 되도록 해줘야 합니다. 

 

---

#include <iostream>
#include <vector>
#include <queue>
 
#define MAX_N 501
using namespace std;
 
//게임 개발 
//위상정렬 
int n, indegree[MAX_N], build_time[MAX_N], ans[MAX_N];
vector<int> faster[MAX_N];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin  >> n;
 
    for (int i =1; i <= n; i++) {
        int tmp, seq;
        cin >> tmp; //건물 짓는데 걸리는 시간 
        build_time[i] = tmp;
        ans[i] = tmp; //누적합을 위해 사용 
 
        cin >> seq;
        while(seq != -1) {
            faster[seq].push_back(i);
            //i가 seq 다음에 지어짐 
            indegree[i]++; //값이 클 수록 늦게 지어진다. 
            cin >> seq;
        }
    }
    //input 
 
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
 
    while(!q.empty()) {
        int now = q.front(); q.pop();
 
        for (int i = 0; i < faster[now].size(); i++) {
            //now 다음에 지어지는 건물들의 번호들 
            int next = faster[now].at(i);
 
            indegree[next]--;
            if(indegree[next] == 0) {
                q.push(next);
            }
 
            //건물들은 먼저 지어져야 하는 건물들이 지어지고 난 후에 지어진다. (여기에서는 now 다음에 지어짐 )
            ans[next] = max(ans[next], ans[now] + build_time[next]);
            //만약 A,B가 끝나는 시간이 다르다면 둘 중 늦게 끝나는 시간 + C를 짓는데 걸리는 시간이 답이 되어야 합니다.
        }
    }
 
    for (int i =1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}