[BOJ] 1516번 | 게임 개발 (C++)

 

🔗문제 보러가기

1516번: 게임 개발

 

🧑‍💻풀이 과정

 

동적 계획법(Dynamic Programming)과 위상 정렬(Topological Sort)를 사용해 풀 수 있습니다.

진입 차수가 0인 노드(v)에서 다른 인접 노드(other)로 향할 때, 다음 로직만 추가해주면 됩니다.

*constructionTimes[i] : i 번째 건물의 건설 시간

*answers[i] : 먼저 지어야 하는 건물을 짓고 난 후, i 번째 건물까지 짓는 데 걸리는 최소 시간

 

answers[other] = max(answers[other],  answers[v] + constructionTimes[other])

 

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

vector<vector<int>> Graph;
vector<int> ConstructionTimes;
vector<int> InDegrees;

vector<int> Solution(int N) {
    vector<int> answers(N + 1);
    queue<int> buildings;

    for (int i = 1; i <= N; i++) {
        if (InDegrees[i] == 0) {
            buildings.push(i);
            answers[i] = ConstructionTimes[i];
        }
    }

    for (int i = 1; i <= N; i++) {
        int v = buildings.front();
        buildings.pop();

        for (const auto& other : Graph[v]) {
            answers[other] = max(answers[other], answers[v] + ConstructionTimes[other]);

            if (--InDegrees[other] == 0)
                buildings.push(other);
        }
    }

    return answers;
}

int main() {
    FAST_IO
    int N, constructionTime, preBuilding;
    cin >> N;

    Graph.resize(N + 1);
    ConstructionTimes.resize(N + 1);
    InDegrees.resize(N + 1);

    for (int i = 1; i <= N; i++) {
        cin >> constructionTime;
        ConstructionTimes[i] = constructionTime;

        while (true) {
            cin >> preBuilding;
            
            if (preBuilding == -1)
                break;
            Graph[preBuilding].emplace_back(i);
            InDegrees[i]++;
        }
    }

    vector<int> answers = Solution(N);
    for (int i = 1; i <= N; i++)
        cout << answers[i] << "\n";

    return 0;
}