백준 1516 게임 개발 | C++

 

 

이번 포스팅은 백준 1516번 게임 개발입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/1516

1516번: 게임 개발

 

 

 

기본 알고리즘

위상 정렬 Topological Sort

 

풀이

최소 시간을 갱신하는 조건 

line56

result[next] = max(result[next], result[cur] + time[next]); 

 

정점 next의 최소 건설 시간은 선행 정점이 모두 지어진 시간에 자신의 건물을 짓는 시간을 더한 값이다.

 

정점4의 갱신 상황에서

정점 4는 정점1과 정점3이 모두 건설되어야 건설할 수 있다.

cur=3일 때

result[next] : 14                                //cur=1일 때 갱신된 값 (10+4)

result[cur] + time[next] : 18        //14(=선행 정점3의 최소 시간) + 4(=건설 소요 시간)

 

최종 result[4] = 18 

 

 

 

전체 코드

 

//백준1516 게임 개발                                                        
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main() {
    /*입력*/
    int N;
    cin >> N;
    
    vector<int> v[501];
    for (int i = 1; i <= N; i++) {
        int input;
        cin >> input;
        while (input != -1) {
            v[i].push_back(input);
            cin >> input;
        }
    }
 
    /*각 건물을 짓는데 걸리는 시간*/
    int time[501];
    for (int i = 1; i <= N; i++) {
        time[i] = v[i][0];
    }
 
    /*위상 정렬*/
    vector<int> adj[501];
    int inDeg[501] = { 0, };
    queue<int> q;
    int result[501]; //출력배열 - 각 건물이 완성되기까지 걸리는 최소 시간
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j < v[i].size(); j++) {
            adj[v[i][j]].push_back(i);
            inDeg[i]++;
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (inDeg[i] == 0) {
            q.push(i);
        }
        result[i] = time[i];
    }
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 0; i < adj[cur].size(); i++) {
            int next = adj[cur][i];
            inDeg[next]--;
            
            result[next] = max(result[next], result[cur] + time[next]); //★
 
            if (inDeg[next] == 0) {
                q.push(next);
            }
        }
    }
 
    /*출력*/
    for (int i = 1; i <= N; i++) {
        cout << result[i] << endl;
    }
 
    return 0;
}