2056-작업

www.acmicpc.net/problem/2056

2056번: 작업

해당 문제는 위상 정렬 알고리즘을 이용하여 풀 수 있습니다. 풀이는 다음과 같습니다.

 

1. 수행 가능한 순대로 작업을 수행한다. 이때, 동시에 수행가능한 작업은 동시에 수행한다.

2. 각 작업을 수행하였을때 걸린 최대 시간을 기록한다. 

3. 각 작업을 수행하였을때 걸린 최대 시간 중 최대 시간을 출력한다.

 

모든 작업을 완수하는데 걸린 최소 시간을 구해야 하는데 풀이에선 최대 시간을 구하는 느낌이 듭니다. 이렇게 구하는 이유는 어떤 작업들이 동시에 수행가능한 경우, 작업들을 마치기 위해서 드는 시간은 결국에 가장 긴 시간이 걸리는 작업을 수행하는데 필요한 시간과 동일하기 때문입니다. 이점을 잘 생각해서 문제를 접근하시면 풀이 과정을 이해하실 수 있을 것입니다. 동시에가 핵심입니다!!

 

테스트 케이스를 통과했음에도 불구하고 제출시 "틀렸습니다"가 출력되는 경우 아래의 입력에 대해 출력값을 확인해보시길 바랍니다.

 

입력

4
10 0
6 1 1
7 1 1
5 1 2

 

출력

21

 

아래의 그림은 위 입력값에 따라 형성되는 작업간의 관계를 그래프(Directed Acyclic Graph)로 표현한 것이며, 모든 작업을 최소시간으로 수행했을때를 작업이 수행되는 순서를 시각화한 그림입니다.

 

 

코드

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

int N;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    //freopen("2056.txt", "r", stdin);
    cin >> N;


    vector<vector<int>> g(N+1);
    vector<int> indegree(N+1, 0);
    vector<int> time(N+1, 0);
    vector<int> sum(N+1, 0); //sum[i]: i 번째 일을 완수했을때 최대로 걸리는 시간

    queue<int> q;
    
    for(int idx_process = 1; idx_process <= N; idx_process++)
    {
        int num_predecessors;
        
        cin >> time[idx_process];        
        cin >> num_predecessors;

        for(int i = 0; i < num_predecessors; i++)
        {
            int idx_predecessor_process;
            cin >> idx_predecessor_process;

            g[idx_predecessor_process].push_back(idx_process);
            indegree[idx_process]++;
        }
    }

    for(int i = 1; i <= N; i++)
        if(indegree[i] == 0)
        {
            q.push(i);
            sum[i] = time[i];
        }

    while(!q.empty())
    { 
        int idx_process = q.front(); 
        q.pop();
        
        for(int idx_next_process:g[idx_process])
        {
            sum[idx_next_process] = max(sum[idx_next_process], sum[idx_process] + time[idx_next_process]);
            
            indegree[idx_next_process] -= 1;
            if(indegree[idx_next_process] == 0)
            {
                q.push(idx_next_process);
            }
        }
    }
    
    int answer = *max_element(std::begin(sum), std::end(sum));

    cout << answer;

    return 0;
}