백준 1005번 ACM Craft [C++]

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

1005번: ACM Craft

#문제 간단 정리

위상정렬을 사용해 문제를 풀자.

#전체 코드

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

using namespace std;

int main() {
    int T;
    cin >> T;

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

        vector<int> build_time(N + 1, 0);
        vector<int> indegree(N + 1, 0);
        vector<int> result(N + 1, 0);
        vector<vector<int>> adj(N + 1);

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

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

        int W;
        cin >> W;

        queue<int> q;
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                q.push(i);
                result[i] = build_time[i];
            }
        }

        while (!q.empty()) {
            int current = q.front();
            q.pop();

            for (int next : adj[current]) {
                result[next] = max(result[next], result[current] + build_time[next]);
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }

        cout << result[W] << '\n';
    }

    return 0;
}

#코드해설

while (!q.empty()) {
            int current = q.front();
            q.pop();

            for (int next : adj[current]) {
                result[next] = max(result[next], result[current] + build_time[next]);
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }

위상정렬 핵심부분

1. while (!q.empty()) { ... }:
   • 큐 q에는 현재 짓기 시작할 수 있는 건물들의 번호가 저장됩니다. (선행 건물이 없는, 즉 현재 지을 수 있는 건물)
2. int current = q.front(); q.pop();:
   • 큐의 가장 앞에 있는 건물 번호를 가져와 current에 저장하고, 해당 건물 번호를 큐에서 제거합니다.
3. for (int next : adj[current]) { ... }:
   • 현재 건물(current)을 짓고 나서 지을 수 있는 후속 건물들을 순회합니다. 여기서 adj는 인접 리스트로, 각 건물에서 다음에 지을 수 있는 건물들의 목록을 저장하고 있습니다.
4. result[next] = max(result[next], result[current] + build_time[next]);:
   • next 건물을 짓기 시작하기 전까지의 누적 시간을 result[next]에 저장합니다. 여기서 중요한 점은, next 건물을 짓기 시작하는 시간이 여러 경로로 인해 다를 수 있기 때문에 그 중 가장 늦은 시간을 선택해야 합니다. 이를 위해 max 함수를 사용합니다.
5. indegree[next]--;:
   • next 건물로 들어오는 간선의 수(indegree)를 하나 줄입니다. 이는 current 건물이 지어졌기 때문에 next 건물로의 선행 조건이 하나 줄어들었음을 나타냅니다.
6. if (indegree[next] == 0) { q.push(next); }:
   • 만약 next 건물로 들어오는 선행 조건이 모두 해소되었다면 (즉, 모든 선행 건물들이 지어졌다면), next 건물도 지을 수 있게 되므로 큐 q에 추가합니다.

이 알고리즘을 통해 선행 건물들의 건설 완료 시간을 고려하여 각 건물을 건설하는 데 필요한 최소 시간을 result 배열에 저장할 수 있습니다.