백준 2056 작업 (C++)

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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> g[10001];
vector<int> t;
vector<int> indeg;
vector<int> res;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int ans = -1;

    cin >> n;

    t.resize(n + 1);
    indeg.resize(n + 1, 0);

    for (int i = 1; i <= n; i++) {

        cin >> t[i];

        int inCnt;
        cin >> inCnt;

        for (int j = 0; j < inCnt; j++) {
            int temp;
            cin >> temp;
            g[temp].push_back(i);
            indeg[i]++;
        }
    }

    queue<int> q;
    res.resize(n + 1);

    for (int i = 1; i <= n; i++) {
        if (!indeg[i]) {
            q.push(i);
        }
        res[i] = t[i];
    }



    while (!q.empty()) {

        int cur = q.front();
        q.pop();

        for (int i = 0; i < g[cur].size(); i++) {

            indeg[g[cur][i]]--;
            res[g[cur][i]]=max(res[g[cur][i]], res[cur]+t[g[cur][i]]);

            if (!indeg[g[cur][i]]) {
                q.push(g[cur][i]);
            }
        }

    }

    for (int i = 1; i <= n; i++) {
        ans = max(ans, res[i]);
    }

    cout << ans;

    return 0;
}

1. 문제

n개의 작업이 걸리는 시간, 해당 작업 이전에 선행되어야 할 작업이 주어진다. 서로 선행 관계가 없는 작업은 동시에 수행이 가능하다. 작업 중에는 선행 관계가 없는 작업이 하나 이상 존재한다. 이 때, 모든 작업을 수행하는 데 걸리는 최소 시간을 구하라.

2. 풀이

선행 작업의 관계가 있으므로 위상 정렬을 이용하여 풀 수 있다. 

    for (int i = 1; i <= n; i++) {

        cin >> t[i];

        int inCnt;
        cin >> inCnt;

        for (int j = 0; j < inCnt; j++) {
            int temp;
            cin >> temp;
            g[temp].push_back(i);
            indeg[i]++;
        }
    }

각 작업에 걸리는 시간을 저장, 선행 작업이 먼저이므로 그래프에는 temp->i의 방향으로 저장, 선행작업의 개수 indeg를 세어준다.

 queue<int> q;
    res.resize(n + 1);

    for (int i = 1; i <= n; i++) {
        if (!indeg[i]) {
            q.push(i);
        }
        dp[i] = t[i];
    }

큐를 만들어 선행 관계가 없는 작업을 추가, dp 배열을 초기화해준다. dp[i]는 각 작업을 하는 데 걸리는 시간이다.

while (!q.empty()) {

        int cur = q.front();
        q.pop();

        for (int i = 0; i < g[cur].size(); i++) {

            indeg[g[cur][i]]--;
            dp[g[cur][i]]=max(dp[g[cur][i]], dp[cur]+t[g[cur][i]]);

            if (!indeg[g[cur][i]]) {
                q.push(g[cur][i]);
            }
        }

    }

큐에서 하나씩 빼주며 위상 정렬을 수행한다. 그리고 dp로 다음 작업을 수행하는 데 걸리는 시간을 갱신하는 데, 선행 작업을 모두 수행해야 하므로 선행 작업을 모두 하고 다음 작업을 하는 시간과 비교해준다.

    for (int i = 1; i <= n; i++) {
        ans = max(ans, res[i]);
    }

    cout << ans;

모든 작업이 끝나는 데 걸리는 시간을 출력해야 한다. 모든 시간 중 가장 늦게 끝나는 작업의 시간이 곧 모든 작업을 끝내는 데 걸리는 시간이므로 계산하여 출력해준다.