[백준 1005] ACM Craft, C++

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

1005번: ACM Craft

본 문제는 DAG(topology sort)를 구현하는 문제다. 각 작업마다 필요한 선행작업 개수를 구하고, 선행작업이 0인 작업 부터 탐색한다. 탐색을 완료할 때 마다 다음 작업을 1씩 감소하여 0이 될때 queue에 추가한다. 자세한 설명은 주석 처리하였다.

#include <cstdio>
#include <queue>
#include <vector>
 
using namespace std;
 
int is_right[1001] = { 0 };
int d[1001];
int a[1001];
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &d[i]);
            a[i] = d[i];
        }
 
        vector<int> v[1001];
        for (int i = 0; i < m; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            v[x].push_back(y);
            // 선행 작업의 개수를 구한다.
            is_right[y] += 1;
        }
 
        int w;
        scanf("%d", &w);
 
        queue<int> q;
        for (int i = 1; i <= n; i++) {
            // 선행 작업이 없는 작업을 queue에 저장
            if (is_right[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int k = 0; k < v[node].size(); k++) {
                int next = v[node][k];
                is_right[next] -= 1;
                // 작업이 오래걸리는 경우를 계산
                if (a[next] < a[node] + d[next]) a[next] = a[node] + d[next];
                // 선행작업을 모두 완료했을 때, queue에 저장
                if (is_right[next] == 0) q.push(next);
            }
        }
        printf("%d\n", a[w]);
    }
}