[ 백준 1005 ] ACM Craft (c/c++)

https://www.acmicpc.net/problem/1005

 

 

[ 문제 요약 ]

건물의 건설 순서가 주어질 때 특정 건물을 가장 빨리 지을 때까지 걸리는 최소시간을 출력한다.

 

 

[ 문제 풀이 ]

1. 건물의 건설 순서를 지켜야 하기 때문에 위상 정렬을 한다.

2. 위상 정렬을 하는 과정에서 가장 건설 시간이 긴 건물을 기다리면 다른 건설은 끝났기 때문에 DP를 이용해서 dp[i], dp[cur] + D[i] 중 큰 값을 저장한다.

3. indegree가 0이 된 값들을 큐에 넣는다.

4. 테스트 케이스가 여러 번 주어지기 때문에 초기화 해준다.

 

 

[ 소스 코드 ]

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

int t, N, K, W;
int D[1010], IN[1010], dp[1010];
vector<int> v[1010];

int main() {
    cin >> t;
    while (t--){
        cin >> N >> K;
        for (int i=1; i<=N; i++) cin >> D[i];
        for (int i=1; i<=K; i++){
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
            IN[b] += 1;
        }
        cin >> W;

        queue<int> q;
        for (int i=1; i<=N; i++){
            if(!IN[i]) {
                q.push(i);
                dp[i] = D[i];
            }
        }
        while (!q.empty()){
            int cur = q.front(); q.pop();
            for (auto i : v[cur]) {
                dp[i] = max(dp[i], dp[cur] + D[i]);
                if (!--IN[i]) q.push(i);
            }
        }

        cout << dp[W] << "\n";
        fill(D, D + N + 1, 0);
        fill(IN, IN + N + 1, 0);
        fill(dp, dp + N + 1, 0);
        for (int i=0; i<1010; i++) v[i].clear();
    }
    
    return 0;
}

 

 

[ 주의할 점 ]

위상 정렬을 하는 도중에 건물의 건설 시간을 DP로 처리하기만 하면 되는 문제였다.