백준 1516번 - 게임 개발

www.acmicpc.net/problem/1516

1516번: 게임 개발

 

다음은 위상정렬의 개념을 이해했다고 가정한 풀이설명입니다.

 

 

문제의 조건을 토대로 <예제 입력 1>의 건물을 짓기위한 순서를 그래프로 표현하면 다음과 같습니다.

 

예제1의 그래프

 

문제의 조건을 보면 모든 입력은 위의 그림처럼 방향성이 있는 비순환 그래프(DAG)로 나타낼 수 있고

건물을 짓기 위한 순서를 필요로 하므로 각각의 건물을 완성하기 위한 최소시간은 위상정렬을 이용해 구할 수 있습니다.

 

위상정렬로 순서를 구하는 과정에서 n번건물의 차수가 0이 되어야 순서를 업데이트 할 수 있으므로 그 과정 중 필요한 비용의 최댓값과 n번 건물의 비용을 더하면 n번 건물을 짓기위한 최소비용을 구할 수 있습니다.

 

4번 건물을 예로들면 4번 건물의 차수는 2이고 그중 1번을 짓기까지 필요한 시간은 10, 3번을 짓기까지 필요한 시간은 14 이므로 10과 14중 최댓값인 14와 4번건물의 건설시간 4를 더하여 최소비용 18이라는 결과를 얻을 수 있습니다.

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;

int N;
vector<int> adj[501]{}; // 그래프
int cost[501]{}; // n번째 건물의 건설시간
int deg[501]{}; // 차수
int ans[501]{}; // n번째 건물 완성까지 필요한 최소시간

// 위상정렬
void topology(){
    queue<int> q;
    for(int i=1; i<=N; i++){
        if(!deg[i]) {
            ans[i] = cost[i];
            q.push(i);
        }
    }

    for(int i=1; i<=N; i++){
        int cn = q.front();
        q.pop();

        for(auto next : adj[cn]){
            ans[next] = max(ans[next], cost[next] + ans[cn]);
            if(--deg[next]==0) q.push(next);
        }
    }
    
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N;
    int n;
	for (int i = 1; i <= N; i++) {
		cin >> cost[i];
		while (1) {
			cin >> n;
			if (n == -1) break;
			adj[n].push_back(i);
			deg[i]++;
		}
	}

    topology();
    for (int i = 1; i <= N; i++)
        cout<<ans[i]<<'\n';
}