[백준/C++] #1005 ACM Craft (DP)

문제

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

구상

문제를 보다가 문득 그래프는 없겠지..?라는 생각이 들었다. 만약 그래프에 사이클이 존재한다면, 사이클을 이루는 건물들 간에는 순환 의존 관계가 형성된다. 즉, 건물 A를 짓기 위해 건물 B가 필요하고, 건물 B를 짓기 위해 건물 C가 필요하며, 건물 C를 짓기 위해 다시 건물 A가 필요하게 되는 모순이 발생한다. 이러한 상황에서는 어떤 건물도 완성될 수 없으므로 건물 건설이 불가능하다. 문제에서 모든 건물이 완성될 수 있다고 나와있었기에 그래프에 사이클이 포함되지 않는다는 것을 확증할 수 있었다.!!

구한 이전 건물의 건설 소요시간을 구했다면 다음 건물의 소요시간을 구하는 로직만 짜면 되기에 dp 알고리즘을 사용하는 문제라는 생각이 들었다.

일단 진입차수가 0인 건물들(이전에 세워야할 건물이 없는 건물들 혹은 이미 이전 건물을 지어 건설이 가능하진 건물들)은 일단 자신의 건물 세우는 시간을 고려하면 되기에 진입 차수가 처음부터 0이었건 0이 되었건 큐에 넣었다. 즉, 건물의 최종 건설 시간을 구한 건물들을 큐에 넣어 해당 건물로부터 다음에 지어질 수 있는 건물들의 시간을 모두 계산하고자 한 것이다.

이때 중요했던 점이 현재 계산한 건물의 진입차수를 1씩 감소시키는 것이었는데, 1씩 감소시키다가 해당 건물의 진입 차수가 0이 되면, 해당 건물의 최종 건설 시간이 도출되었다는 뜻으로, 해당 건물을 통해 또 다른 건물을 지을 수 있게되었다는 뜻이다. 그렇게 진입차수가 0이 된 건물은 큐에 넣어 다음 건물 계산을 위해 사용된다. 

 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<queue>
#define MAX 101
#define INF 987654321
#define endl "\n"
using namespace std;
/*
1005 acm craft
건물을 짓는 순서가 정해져있지 않다. 게임에 따라 달리 주어지고, 게임 시작 시 건물을 짓는 순서가 주어진다. 
모든 건물은 각각 건설으 시작하여 완성이 될 때까지 delay가 존재한다. 

특정 건물을 가장 빨리 지을때까지 걸리는 최소 시간을 알아내는 프로그램
*/

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int T; // 테스트 케이스 수
    cin >> T;

    while (T--) {
        int N, K, W;
        cin >> N >> K;

        vector<int> time(N + 1); // 각 건물의 건설 시간을 저장
        vector<int> indegree(N + 1, 0); // 각 건물의 진입 차수
        vector<vector<int>> graph(N + 1); // 건물 간의 건설 순서를 저장

        for (int i = 1; i <= N; i++) {
            cin >> time[i];
        }

        for (int i = 0; i < K; i++) {
            int X, Y;
            cin >> X >> Y;
            graph[X].push_back(Y);
            indegree[Y]++;
        }

        cin >> W;

        queue<int> q;
        vector<int> dp(N + 1, 0);

        // 진입 차수가 0인 건물들을 큐에 넣는다.
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                q.push(i);
                dp[i] = time[i]; // 시간 갱신
            }
        }

        // 위상 정렬을 수행하면서 건물 건설 시간을 계산
        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            for (int next : graph[curr]) {
                dp[next] = max(dp[next], dp[curr] + time[next]); // 이전 건물들 세우는 시간 + 내 건물 세우는 시간에서 가장 큰 값
                indegree[next]--;

                if (indegree[next] == 0) { // 딱 0일때만 넣기에 반복도 안되고, 딱 이전 모든 건물이 세워진 다음 건물만 큐에 들어감
                    q.push(next);
                }
            }
        }

        // 결과 출력
        cout << dp[W] << endl;
    }

    return 0;
}