[백준/BOJ] 2056 작업

문제 : 2056 작업

2056번: 작업

각 작업의 수행 시간과 선행 작업을 할당받았을 때,

작업이 끝나는 최단시간을 출력하는 문제이다.

위상 정렬을 사용해 현재 작업할 수 있는 것부터 순차적으로 작업하면서

각 작업의 최소 시간을 구한 후 그중 최댓값을 찾으면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, T[10005], chk[10005], ans[10005];
vector<ll> arr[10005];
ll TopologySort(){
    ll ret=0;
    queue<ll> q;
    for (int i=1;i<=N;i++){
        if (chk[i]==0)
            q.push(i);
    }
    for (int i=1;i<=N;i++){
        ll x=q.front();
        q.pop();
        ans[x]+=T[x];
        for (int j=0;j<arr[x].size();j++){
            ll dx=arr[x][j];
            ans[dx]=max(ans[x],ans[dx]);
            if (--chk[dx]==0)
                q.push(dx);
        }
    }
    for (int i=1;i<=N;i++){
        ret=max(ans[i],ret);
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i=1;i<=N;i++){
        cin >> T[i];
        cin >> M;
        for (int j=0;j<M;j++){
            ll a;
            cin >> a;
            arr[a].push_back(i);
            chk[i]++;
        }
    }
    cout << TopologySort();
    return 0;
}