(C++) 백준 2056 작업

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

int arr[10005]; // 작업에 걸리는 시간 저장 
int T[10005]; // 끝난 시간 저장 
bool check[10005][10005]; // 선행되어야 하는 작업 확인
bool isbuilt[10005]; // 작업 처리여부 확인
queue<int> q; // 작업이 모두 완료되었는지 확인하기 위한 큐
vector<vector<int>> v(10005); // 선행되어야 하는 작업 확인

그리고 큐가 empty 될때까지 다음 로직을 반복했다.
선행 작업 확인 (배열로)

(1) 선행작업이 모두 완료되었거나 없음

• 선행작업이 없는 경우, 끝난시간은 작업시간과 같음
• 선행작업이 있는 경우, 끝난시간은 선행시간 중 가장 늦게끝난 시간+작업시간

(2) 선행작업이 완료되지 않은 경우가 있음

• 다시 큐에 넣고 다음 작업에 대해 확인

정답은 가장 큰 배열 T의 값이다.

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

int arr[10005];
int T[10005]; // 끝난 시간
bool check[10005][10005];
bool isbuilt[10005];
queue<int> q;
vector<vector<int>> v(10005);


int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin>>N;

    for(int i=1; i<=N; i++){
        q.push(i);
        cin>>arr[i];
        int k,x;
        cin>>k;
        for(int j=0; j<k; j++) {
            cin>>x;
            check[i][x]=true;
            v[i].push_back(x);
        }
    }

    while(!q.empty()){

        int tmp = q.front();
        q.pop();
        bool flag=true;

        for(int i=1; i<=N; i++) if(check[tmp][i]) {
            if(!isbuilt[i]) {
                flag=false;
                break;
            }
        }

        if(!flag) {
            q.push(tmp);
            continue;
        }

        if(v[tmp].empty()) {
            T[tmp]=arr[tmp];
            isbuilt[tmp]=true;
            continue;
        }

        int MAX=0;
        for(int i=0; i<v[tmp].size(); i++) {
            if(MAX<T[v[tmp][i]]) MAX=T[v[tmp][i]];
        }

        T[tmp]= MAX+arr[tmp];
        isbuilt[tmp]=true;
    }


    int ans=0;
    for(int i=1; i<=N; i++) ans = max(ans, T[i]);

    cout<<ans;

}