백준 2056번 작업 - C++(cpp) 풀이

1. 각 작업을 정점으로, 작업 순서를 방향 간선으로 나타낸다.
2. 그래프에 대해 위상 정렬을 한다.
3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 작업에 걸리는 시간을 구한다.
4. max(totalCost[i])를 출력한다.

---

 1516번 게임 개발 문제와 똑같으니 1,2,3번 풀이는 아래에서 확인!

백준 1516번 게임 개발 - C++(cpp) 풀이

 

4. max(totalCost[i])를 출력한다.

 1516번과의 차이점은, "모든 작업"을 완료하기 위해 필요한 시간을 출력해야 한다는 것이다. totalCost가 가장 큰 작업이 가장 늦게 끝날 것이므로 max(totalCost)를 출력해주면 된다.

---

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

using namespace std;

int N, maxTotalCost;
int indegree[10001], cost[10001], totalCost[10001];
vector<int> edges[10001];

int topologySort() {
    queue<int> q;
    
    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0) {
            q.push(i);
            totalCost[i] = cost[i];
            maxTotalCost = max(maxTotalCost, totalCost[i]);
        }
    }
    
    while (!q.empty()) {
        int current = q.front(); q.pop();
        
        maxTotalCost = max(maxTotalCost, totalCost[current]);
        
        for (int i = 0; i < edges[current].size(); i++) {
            int end = edges[current][i];
            totalCost[end] = max(totalCost[end], totalCost[current] + cost[end]);
            indegree[end]--;
            if (indegree[end] == 0) q.push(end);
        }
    }
    
    return maxTotalCost;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int c, edgeCount, end; 
    
    cin >> N;

    for (int i=1; i<=N; i++) {
        cin >> c;
        cost[i] = c;
        
        cin >> edgeCount;
        for(int j=0; j<edgeCount; j++) {
            cin >> end;
            edges[i].push_back(end);
            indegree[end]++;
        }
    }
    
    cout << topologySort();

    return 0;
}