백준 1516번 게임 개발 - C++(cpp) 풀이

1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다.
2. 그래프에 대해 위상 정렬을 한다.
3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물을 짓는 데 걸리는 시간을 구한다.

---

1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다.

 이렇게 선행 관계가 정해져있는 작업들을 순서대로 수행하는 상황은 그래프 위상 정렬 알고리즘으로 해결할 수 있다. 먼저 주어진 상황을 그래프로 나타낸다. 

 

2. 그래프에 대해 위상 정렬을 한다.

위상 정렬을 해준다. 아래 코드에서는 큐를 사용하였고, 선행 작업들이 모두 완료된 작업들만 큐에 들어가게 된다.

 

3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물을 짓는 데 걸리는 시간을 구한다.

 totalCost[i]는 i번 건물이 "완성"되기까지 걸리는 시간으로 둔다. totalCost[i]는 선행 건물들 중 totalCost가 가장 큰 건물의 totalCost + i번 건물 하나를 단독으로 짓는 데 걸리는 시간(cost[i])만큼이 된다. max(totalCost[prev])를 구하기 위해 indegree를 업데이트할 때마다 totalCost값을 계산하여 최댓값으로 유지되게 한다.

---

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

using namespace std;

int N;
int indegree[501], cost[501], totalCost[501];
vector<int> edges[501];

void topologySort() {
    queue<int> q;
    
    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0) {
            q.push(i);
            totalCost[i] = cost[i];
        }
    }
    
    while (!q.empty()) {
        int current = q.front(); q.pop();
        
        for (int i = 0; i < edges[current].size(); i++) {
            int end = edges[current][i];
            totalCost[end] = max(totalCost[end], totalCost[current] + cost[end]);
            indegree[end]--;
            if (indegree[end] == 0) q.push(end);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int c, prev; 
    
    cin >> N;

    for (int i=1; i<=N; i++) {
        cin >> c;
        cost[i] = c;
        
        while (1) {
            cin >> prev;
            
            if (prev == -1) break;
            
            edges[prev].push_back(i);
            indegree[i]++;
        }
    }
    
    topologySort();
    
    for (int i=1; i<=N; i++) {
        cout << totalCost[i] << "\n";
    }

    return 0;
}