[백준 1005] ACM Craft C++

1005번: ACM Craft

위상 정렬, 다이나믹 프로그래밍

---

1. 문제해결 아이디어

indegree를 활용한 위상 정렬을 하는 문제이다.

위 그림에서 각각의 phase는 다음 phase로 넘어가기위해 모두 해결해야하는 과제와도 같다.

예를 들어서 phase2에서 phase3로 넘어가려면 phase2에 있는 건물을 모두 건설해야 넘어갈 수 있다.

따라서 phase2에서 가장 오래걸리는 건물이 해당 phase에서 걸리는 시간이 되고,

이전 phase의 최대 시간만큼만 next phase의 작업시간에 추가된다. 

 

phase를 구분하는 방식은 BFS를 사용한다.

현재 loop에서 탐색가능한 모든 건물을 자동으로 같은 phase로 만들어주기 때문이다.

dp[i] : i번 건물을 건설하는데 걸리는 시간

 

// next 건물을 건설하기 위한 시간 = 현재 phase를 통과하는데 걸리는 시간 + 다음 건물의 건설시간

dp[next] = dp[now] + times[next];

위와 같은 점화식을 통해서 W 번째 건물을 건설하기 위한 최소 시간을 알 수 있다.

---

2. 코드

여러개의 TestCase가 주어지기 때문에 class를 사용했다.

현재 case에 대한 객체 하나만 만들어주고 BFS를 돌리면 답이 나오니 main함수가 깔끔해진 모습이다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
class ACM{
    int N, K, X, Y, W;
    vector<int> times, indg, dp;
    vector< vector<int> > graph;
public:
    ACM(){
        cin >> N >> K;
        times.resize(N+1);
        graph.resize(N+1);
        indg.resize(N+1, 0);
        dp.resize(N+1, 0);
        for(int i = 1; i <= N; i++){
            cin >> times[i];
        }
        for(int i = 0; i < K; i++){
            cin >> X >> Y;
            graph[X].push_back(Y);
            indg[Y]++;
        }
        cin >> W;
    }
    
    void BFS(){
        queue<int> que;
        //indegree가 0인 원소들을 que에 넣어준다
        for(int i = 1; i <= N; i++){
            if(indg[i] == 0){
                que.push(i);
                dp[i] = times[i];
            }
        }
        
        while(!que.empty()){
            int now = que.front();
            que.pop();
            if(now == W) break;
            
            for(int i = 0; i < graph[now].size(); i++){
                int next = graph[now][i];
                if(--indg[next] == 0){
                    que.push(next);
                }
                if(dp[next] < dp[now] + times[next]){
                    dp[next] = dp[now] + times[next];
                }
                
            }
        }
        cout << dp[W] << "\n";
    }
};
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int test;
    cin >> test;
    while(test--){
        ACM A1;
        A1.BFS();
    }
    return 0;
}
 

위상정렬에 DP개념이 섞여있는 재미있는 문제였다.

화이팅