백준 1005 ACM Craft (C++)

1005번: ACM Craft

위상 정렬을 할 줄 안다면 어렵지 않게 풀 수 있는 문제이다. 나는 BFS를 통한 위상 정렬을 이용했다. 위상 정렬을 통해 처음부터 W까지 순차적으로 방문하면서 방문한 정점의 가중치, 즉 건설 시간을 누적으로 합하여 int dp[1001]에 저장하였다. 최종 건설 시간은 결국 간선이 연결된 정점들의 최대 가중치의 합이므로 최댓값을 찾아 저장해주고 dp[W]에 최종 시간이 남게 된다.
위상 정렬 문제는 전에 한번 풀어봤기에 알고리즘을 생각하는데는 어려움이 없었지만 가중치 합을 구하는 과정에서 시간이 좀 오래 걸렸다. dp 문제를 좀 더 풀어봐야겠다.

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

using namespace std;

int T, N, K, W;
int D[1001];
vector<int> v[1001];
int inDegree[1001];
int dp[1001];

void solution() {
    queue<int> q;
    
    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
            dp[i] = D[i];
        }
    }

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

        q.pop();
        
        if (cur == W) break;

        for (int i = 0; i < v[cur].size(); i++) {
            int next = v[cur][i];

            inDegree[next]--;
            dp[next] = max(dp[next], dp[cur] + D[next]);

            if (inDegree[next] == 0) {
                q.push(next);
            }
        }
    }

    cout << dp[W] << endl;
}

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

    cin >> T;

    while (T--) {
        memset(D, 0, sizeof(D));
        memset(v, 0, sizeof(v));
        memset(inDegree, 0, sizeof(inDegree));
        memset(res, 0, sizeof(res));

        cin >> N >> K;

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

        for (int i = 0; i < K; i++) {
            int a, b;
            cin >> a >> b;

            v[a].push_back(b);
            inDegree[b]++;
        }

        cin >> W;

        solution();
    }

    return 0;
}