[BOJ 1005 // C++] ACM Craft

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1005번 문제인 ACM Craft이다.
문제는 아래 링크를 확인하자.

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

1005번: ACM Craft

문제에서 건물을 짓는 순서를 DAG(사이클 없는 방향그래프)로 나타내고, 위상정렬을 통해 이 문제를 해결할 수 있다.

 

글쓴이는 아래와 같이 BFS를 이용하여 위상정렬을 구현해보았다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

vector<int> G[1001];
int work[1001];
int weight[1001];
int cnt[1001];

queue<int> que;

void bfs(int W) {
    while (!que.empty()) {
        int current = que.front();
        que.pop();

        if (current == W) {
            cout << weight[W] + work[W] << '\n';
            return;
        }

        for (auto node : G[current]) {
            weight[node] = max(weight[node], weight[current] + work[current]);
            cnt[node]--;
            if (cnt[node] == 0) que.push(node);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    while (T--) {
        int N, K; cin >> N >> K;
        
        while (!que.empty()) que.pop();

        for (int i = 1;i <= N;i++) {
            G[i].clear();
        }
        
        memset(cnt, 0, sizeof(cnt));
        memset(weight, 0, sizeof(weight));
        
        for (int i = 1;i <= N;i++) {
            cin >> work[i];
        }

        while (K--) {
            int x, y; cin >> x >> y;
            G[x].push_back(y);
            cnt[y]++;
        }

        for (int i = 1;i <= N;i++) {
            if (cnt[i] == 0) que.push(i);
        }

        int W; cin >> W;

        bfs(W);
    }
}