[백준] 2056번 작업

문제: 2056번: 작업

basic-algo-lecture/workbook/0x1A.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x1A.md at master · encrypted-def/basic-algo-lecture

 

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> graph;
vector<int> indeg;
vector<int> workTime;
vector<int> sumWorkTime;

int main() {
    ios::sync_with_stdio(false);
    
    int n; // 수행해야 할 작업
    cin >> n;

    graph = vector<vector<int>>(n + 1); // 0번 인덱스 안 써
    indeg = vector<int>(n + 1);
    workTime = vector<int>(n + 1);
    sumWorkTime = vector<int>(n + 1);

    for (int i = 1; i < n + 1; i++) {
        cin >> workTime[i];

        int workNum;
        cin >> workNum;

        for (int j = 0; j < workNum; j++) {
            int next;
            cin >> next;

            graph[next].push_back(i);
            indeg[i]++;
        }
    }
    queue<int> nexts;
    for (int i = 1; i < n + 1; i++) {
        if (indeg[i] == 0) {
            nexts.push(i);
            sumWorkTime[i] += workTime[i];
        }
    }
    while (!nexts.empty()) {
        int cur = nexts.front(); nexts.pop();

        for (int next : graph[cur]) {
            int updateTime = workTime[next] + sumWorkTime[cur];

            if (updateTime > sumWorkTime[next]) {
                sumWorkTime[next] = updateTime; // 갱신!
            }

            indeg[next]--;
            if (indeg[next] == 0) {
                workTime[next] = sumWorkTime[next];
                nexts.push(next);
            }
        }
    }
    int ans = -1;
    for (int i = 1; i < n + 1; i++) {
        if (ans < sumWorkTime[i]) {
            ans = sumWorkTime[i];
        }
    }
    cout << ans;

    return 0;
}