[Algorithm/C++17] 백준 1005 ACM Craft

문제

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

1005번: ACM Craft

풀이 방법

위상 정렬과 DP에 대해 알고 있어야 하는 문제다. 잘 모르겠다면 바킹독님 블로그나 라이님 블로그를 봐보자. (실제로 내가 알고리즘 공부를 하며 계속 방문중인 블로그들이다.)

 

건설 순서에 따라 위상 정렬을 진행해주면서 각 건물의 최소 건설 시작 시간을 갱신해주면 된다.

 

다시 말해,

dp[i] = i번 건물을 짓기 시작하는 데 걸리는 최소 시간(최소 건설 시작 시간),

buildTime[i] = i번 건물을 짓는데 걸리는 시간으로 놓는다.

예를 들어 예제에서 dp[4] = 110이고 buildTime[4] = 10이다.

 

자신에게 들어오는 간선이 0인 노드들부터 시작해서 dp를 갱신한다.

이때 dp[next] = max(dp[next], dp[cur] + buildTime[cur]) 이다.

최대값을 갖는 이유는 건설 시 앞서 선행된 노드들을 모두 건설 완료해야하고, 건설은 동시에 진행이 가능하기 때문이다.

 

예를 들어 예제에서 4번 건물은 2번, 3번 건물을 모두 건설해야 한다.

따라서 dp[4]가 갱신될 때

2번 건물로부터 dp[4] = dp[2] + buildTime[2],

3번 건물로부터 dp[4] = dp[3] + buildTime[3]을 하게 된다.

이 중 dp[3] + buildTime[3]이 더 크므로 결국 3번 건물을 지으면 자연스럽게 2번 건물도 지을 수 있을 것이고(동시에 진행하니까) 그에 따라 후행 노드인 4번 건물을 지을 수 있는 것이다. 따라서 

따라서 4번 건물의 최소 건설 시작 시간은

dp[4] = max(dp[2] + buildTime[2], dp[3] + buildTime[3]) 인 것이다. 

 

그래서 위상 정렬을 진행할 때 현재 노드가 cur라면 다음 노드가 next라면,

dp[next] = max(dp[next], dp[cur] + buildTime[cur])가 된다.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int N, K, X, Y, W;
        scanf("%d %d", &N, &K);
        vector<int> buildTime(N+1);
        vector<vector<int>> v(N+1, vector<int>());
        vector<int> indegree(N+1, 0);
        
        // 입력
        for(int i=1; i<=N; i++)
        {
            scanf("%d", &buildTime[i]);
        }
        for(int i=0; i<K; i++)
        {
            scanf("%d %d", &X, &Y);
            v[X].push_back(Y);
            indegree[Y]++;
        }
        scanf("%d", &W);
        
        // 위상정렬
        queue<int> q;
        vector<int> dp(N+1);
        for(int i=1; i<=N; i++)
        {
            if(indegree[i] == 0)
                q.push(i);
        }
        while(!q.empty())
        {
            int cur = q.front();
            q.pop();
            for(int i=0; i<v[cur].size(); i++)
            {
                int next = v[cur][i];
                dp[next] = max(dp[next], dp[cur] + buildTime[cur]);
                    
                indegree[next]--;
                if(indegree[next] == 0)
                    q.push(next);
            }
        }
        printf("%d\n", dp[W]+buildTime[W]);
    }
    return 0;
}

고찰

위상정렬은 예전에 잠깐 학습했다가 잊어버리고 다시 문제를 풀어보았는데, dp와 결합한 문제는 처음봐서 좀 난해했다. 하지만 블로그나 백준 질문게시판에 좋은 정보가 워낙 많아서, 찾으려고 하면 쉽게 찾을 수 있던 문제였다.