[백준/C++] 1005번: ACM Craft

문제

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

---

문제 요약

1번부터 N번까지 각 N개의 건물을 짓는데 걸리는 시간이 주어진다.

 

또한 건설 순서 X Y가 주어진다.

(X Y: 건물 X를 지은 다음 건물 Y를 짓는 것이 가능하다.)

 

특정 건물 W를 입력 받고, 해당 건물이 가장 빨리 지을 때까지 걸리는 최소시간을 출력한다.

 

건물들은 가능하다면, 동시에 지어질 수 있다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

// indegree[i]: i번 노드로 들어오는 간선의 수
int indegree[1010];

// delay[i]: i번 노드의 지연 시간
int delay[1010];

// dp[i]: i번 노드를 건설하는 데 걸리는 최소 시간
int dp[1010];

int t, n, k, res, w;

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

    cin >> t;

    while (t--) {
        // edges[a][b]: a -> b 간선
        vector<int> edges[1010];

        // indegree가 0인 노드 번호 저장
        queue<int> q;

        memset(indegree, 0, sizeof(indegree));
        memset(delay, 0, sizeof(delay));
        memset(dp, 0, sizeof(dp));

        res = 0;

        cin >> n >> k;

        // i번 건물을 건설하는데 걸리는 지연 시간
        for (int i = 1; i <= n; i++) {
            cin >> delay[i];
        }

        // 그래프 입력
        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;

            edges[a].push_back(b);
            indegree[b]++;
        }

        cin >> w;

        // 초기 설정
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                q.push(i);

                dp[i] = delay[i];
            }
        }

        // Tropical Sort를 이용한 DP
        while (!q.empty()) {
            int x = q.front();
            q.pop();

            for (int i = 0; i < edges[x].size(); i++) {
                int nx = edges[x][i];

                indegree[nx]--;

                if (indegree[nx] == 0) {
                    q.push(nx);
                }

                // nx로 오는 간선이 여러 개 있다면, 그 중 가장 긴 시간 만큼 기다려야 한다.
                dp[nx] = max(dp[nx], dp[x] + delay[nx]);
            }   
        }

        cout << dp[w] << "\n";

    }

    return 0;
}

---

코드 설명

Topological Sort와 Dynamic Programming를 이용한다.

 

각 테스트케이스마다 필요한 정보들을 입력받는다.

 

건물은 노드, 건설 순서는 간선으로 볼 수 있다.

 

그래프의 간선 정보를 인접 행렬로 edges 벡터에 저장한다.

(edges[a]: a에서 갈 수 있는 노드들)

 

Topological Sort를 위해 indegree 배열을 정의하고, 그래프 정보를 입력받으면서 구한다.

(indegree[i]: i번 노드로 들어오는 간선 수)

 

Dynamic Programming를 위해 dp 테이블을 정의한다.

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

 

초기 설정으로 들어오는 간선 수가 0인 노드를 찾고, 큐에 먼저 삽입한다.

추가로, dp값을 자신의 건물만을 건설하는데 걸리는 시간으로 설정한다.

 

큐에서 요소(노드)를 하나씩 빼면서, 해당 건물(x)을 건설해야만 건설할 수 있는 건물들(nx)을 살펴본다.

 

nx를 건설하기 위해 nx 이전에 연결된 모든 건물들이 건설되어야 한다. 따라서, nx의 dp값은 nx까지 연결되는 여러 경로 중 최대 소요 시간과 같다.(동시에 여러 건물을 지을 수 있으므로 경로를 하나씩 따로 계산해도 된다.)

 

추가로 만약 현재 건설할 수 있는 건물이라면 (indegree가 0인 노드), 큐에 삽입한다.

 

마지막으로, dp[W]를 출력한다.

 

---

고찰

Topological Sort를 통해 노드들을 접근하면서, 각 노드들에 대해 dp테이블을 적용한 점이 매우 인상깊었다!