[C++] 백준 1516: 게임 개발

 

문제 이해

• 각 건물에는 건설 시간이 존재한다.
• 건설은 동시에 진행이 가능하고, 건물 순서상 필요한 건물이 모두 건설되었을 때 다음 건물을 건설할 수 있다.
• N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력하라.

N: 건물의 개수 1 ~ 500(10^2)

Di: 각 건물 건설에 걸리는 시간 1 ~ 100,000(10^5)

 

 

 

풀이

N개의 각 건물을 짓는데 걸리는 최소시간을 구하는 문제이다.

 

각 건물마다 짓는데 걸리는 최소시간을 DP로 저장해놓고,

순서가 주어진 그래프를 위상정렬을 하면 되는 문제이다.

즉, DP와 위상정렬에 대해 둘 다 알고있어야 풀 수 있는 문제였다!

 

1005: ACM Craft 문제와 거의 같은 문제이다.

https://dmoritle.tistory.com/entry/C-1005-ACM-Craft

[C++] 백준 1005: ACM Craft

 

 

 

dp[i] = i번째 건물을 건설하는 데 걸리는 최소시간이라고 가정하자.

그리고 각 건물의 건설시간을 cost라는 배열에 저장해두자.

int dp[505];
int cost[505];

 

 

위상 정렬을 수행하기 위해서는

각 정점까지 연결된 정점의 개수를 나타내는 inDegree 배열과

건설 순서를 저장할 벡터 배열

위상 정렬을 할 때 사용되는 queue가 필요하다.

int inDegree[505];
vector <int> v[505];
queue <int> q;

 

 

이 문제는

3가지 프로세스로 구성되는데

1. 입력

2. 위상 정렬

3. 출력

이다.

 

 

1. 입력

5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

 

 int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        int prev = 0;
        cin>>cost[i];

        while(prev != -1){
            cin>>prev;
            if(prev == -1) break;
            inDegree[i]++;
            v[prev].push_back(i);
        }
    }

cost[i] =  각 건물의 건설시간이라고 할 때,

이전에 건설되어야 할 건물을 입력받아 벡터 배열에 넣는다.

이때 -1이 입력되면 입력이 종료되어야 하므로 그 점을 유의한다.

 

넣고 나면

[1] = {2, 3, 4}

[2] = 

[3] = {4, 5}

[4] = 

[5] = 

와 같이 배열에 들어가있을 것이다.

 

inDegree는 그래프에서 시작점이 아닌 끝점의 값을 키운다.

 

 

2. 위상 정렬

for(int i = 1; i <= n; i++){
        if(inDegree[i] == 0){
            q.push(i);
        }
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();

        dp[now] = max(dp[now], cost[now]);
        for(int i = 0; i < v[now].size(); i++){
            int next = v[now][i];
            inDegree[next]--;
            if(inDegree[next] == 0) q.push(next);
            dp[next] = max(cost[next] + dp[now], dp[next]);
        }
    }

 

자신에게 들어오는 간선이 0인 정점부터 큐에 넣고 while문을 시작한다.

 

dp[now] = max(dp[now], cost[now]);

특정 건물을 지을 때 자신의 건설시간만큼은 소요하므로 그 점을 반영해준다.

 

 

for문을 돌면서, 큐에서 뺀 값을 시작점으로 하는 간선들을 모두 탐색해

dp배열의 값을 수정한다.

 

 

예제를 통해 설명하면

[1] = {2, 3, 4}

[2] = 

[3] = {4, 5}

[4] = 

[5] = 

가 벡터 배열에 들어있는 상태에서

 

inDegree = {0, 1, 1, 2, 1}

inDegree[1] == 0 이므로 1이 큐에 들어간다.

 

1과 연결된 2, 3, 4에 대해 dp값을 수정해주고, inDegree값도 1씩 줄인다.

inDegree = {0, 0, 0, 1, 1}

그럼 2와 3도 큐에 들어가서 위상정렬이 쭉쭉 진행되는 것이다.

 

2 다음 3이 빠지고

inDegree = {0, 0, 0, 0, 0}이 되어

4와 5에 대한 dp 값도 변경될것이다.

 

 

 

이때, 최솟값이니 max가 아닌 min이라고 생각할 수 있지만,

건설 순서에 따라 이전 건물을 모두 짓지 않으면 지을 수 없으므로 max를 써야한다.

 

 

3. 출력

for(int i = 1; i <= n; i++){
        cout<<dp[i]<<"\n";
    }

 

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int dp[505];
int cost[505];
vector <int> v[505];
int inDegree[505];
queue <int> q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        int prev = 0;
        cin>>cost[i];

        while(prev != -1){
            cin>>prev;
            if(prev == -1) break;
            inDegree[i]++;
            v[prev].push_back(i);
        }
    }

    for(int i = 1; i <= n; i++){
        if(inDegree[i] == 0){
            q.push(i);
        }
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();

        dp[now] = max(dp[now], cost[now]);
        for(int i = 0; i < v[now].size(); i++){
            int next = v[now][i];
            inDegree[next]--;
            if(inDegree[next] == 0) q.push(next);
            dp[next] = max(cost[next] + dp[now], dp[next]);
        }
    }

    for(int i = 1; i <= n; i++){
        cout<<dp[i]<<"\n";
    }

    return 0;
}