[C++] 백준 1005: ACM Craft

 

문제 이해

• 건물은 짓는 순서는 매 게임마다 주어진다.
• 각 건물에는 건설 시간이 존재한다.
• 건설은 동시에 진행이 가능하고, 건물 순서상 필요한 건물이 모두 건설되었을 때 다음 건물을 건설할 수 있다.
• 특정 건물을 가장 빨리 건설할 때까지 걸리는 최소 시간을 구하여라.

T: 테스트 케이스

N: 건물의 개수 1 ~ 10^3

K: 건물순서 규칙의 총 개수 1 ~ 10^5

Di: 각 건물 건설에 걸리는 시간 1 ~ 10^5

{X, Y}: 건설 순서

W: 백준이가 승리하기 위해 건설해야 하는 건물의 번호

 

 

풀이

특정 건물을 짓는데 걸리는 최소시간을 구하는 문제이다.

 

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

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

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

 

 

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

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

int dp[1005];
int cost[1005];

 

 

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

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

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

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

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

 

 

이 문제는

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

1. 입력

2. 위상 정렬

3. 초기화

이다.

 

 

1. 입력

4 4
10 1 100 10
1 2
1 3
2 4
3 4
4

 

void input(){
    cin>>n>>k;
    for(int i = 1; i <= n; i++){
        cin>>cost[i];
        dp[i] = cost[i];
    }
    for(int i = 1; i <= k; i++){
        cin>>x>>y;
        v[x].push_back(y);
        inDegree[y]++;
    }
    cin>>w;
}

cost[i] =  각 건물의 건설시간

dp[i] = 각 건물을 건설하는데 걸리는 최소시간이므로

건설 시간으로 세팅해두자.

물론 건설 순서에 따라 위상 정렬을 진행하며 비용은 커질 것이다.

 

그 다음, 건설 순서 {X, Y}를 입력받아

벡터 배열에 넣는다.

넣고 나면

[1] = {2, 3}

[2] = {4}

[3] = {4}

[4] = 

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

 

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

 

 

2. 위상 정렬

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

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

    if(prev == w) cout<<dp[prev]<<"\n";
            
    for(int i = 0; i < v[prev].size(); i++){
            int now = v[prev][i];
            inDegree[now]--;
            if(inDegree[now] == 0){
                q.push(now);
            }
            dp[now] = max(dp[prev] + cost[now], dp[now]);
        }
}

 

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

 

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

dp배열의 값을 수정한다.

 

 

예제를 통해 설명하면

[1] = {2, 3}

[2] = {4}

[3] = {4}

[4] = 

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

 

inDegree[5] = {0, 0, 1, 1, 2}

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

 

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

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

 

 

 

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

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

 

 

3. 초기화

for(int i = 1; i <= n; i++){
        cost[i] = 0;
        dp[i] = 0;
        v[i].clear();
        inDegree[i] = 0;
}

테스트케이스가 여러 개이므로 한 케이스가 끝난 뒤,

반드시 배열의 값들을 초기화해줘야 한다!

 

 

 

전체 코드

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

int dp[1005];
int cost[1005];
int inDegree[1005];
vector <int> v[1005];
queue <int> q;
int n, k, x, y, w;

void input(){
    cin>>n>>k;
    for(int i = 1; i <= n; i++){
        cin>>cost[i];
        dp[i] = cost[i];
    }
    for(int i = 1; i <= k; i++){
        cin>>x>>y;
        v[x].push_back(y);
        inDegree[y]++;
    }
    cin>>w;
}

void arrayClear(){
    for(int i = 1; i <= n; i++){
        cost[i] = 0;
        dp[i] = 0;
        v[i].clear();
        inDegree[i] = 0;
    }
}

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

    int t;
    cin>>t;
    while(t--){
        input();

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

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

            if(prev == w) cout<<dp[prev]<<"\n";
            
            for(int i = 0; i < v[prev].size(); i++){
                int now = v[prev][i];
                inDegree[now]--;
                if(inDegree[now] == 0){
                    q.push(now);
                }
                dp[now] = max(dp[prev] + cost[now], dp[now]);
            }
        }

        arrayClear();
    }

    return 0;
}

잊고 있었던 위상정렬에 대해 기억을 되살려준 문제이다!