[Algorithm]Baekjoon 2056번 :: 작업

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

2056번: 작업

 
int n, prevWorkCount, prevWork;
int workEndTimes[10001] = { 0 };
int workEndTimesIncludingPrevWork[10001] = { 0 };
vector<vector<int>> graph(10001);
int inDegrees[10001] = { 0 };
 
 
int DFS(int node)
{
    if (workEndTimesIncludingPrevWork[node] != -1)
    {
        return workEndTimesIncludingPrevWork[node];
    }
 
    int maxWorkTime = 0;
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
        maxWorkTime = max(maxWorkTime, DFS(nextNode));
    }
 
    return workEndTimesIncludingPrevWork[node] = workEndTimes[node] + maxWorkTime;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> workEndTimes[i];
        cin >> prevWorkCount;
 
        for (int j = 0; j < prevWorkCount; ++j)
        {
            cin >> prevWork;
 
            ++inDegrees[prevWork];
            graph[i].push_back(prevWork);
        }
    }
 
    memset(workEndTimesIncludingPrevWork, -1, sizeof(workEndTimesIncludingPrevWork));
 
    int answer = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (inDegrees[i] == 0)
        {
            answer = max(answer, DFS(i));
        }
    }
 
    cout << answer;
}

 

은근 꽤 자주 나오는 유형의 문제인 것 같다.

최종적으로 모든 작업을 마무리하기위한 최소시간을 구하는 문제이다.

 

최소시간을 구하라고하니까 뭔가 최솟값들을 구해야할 것 같지만, 사실 그렇지는 않다.

특정작업이 마무리되려면 선행작업들이 '모두' 완료되어야 하기 때문에,

하위작업들 중 완료시간이 가장 큰값 + 특정작업 작업시간 => 특정작업이 선행작업까지포함해서 완료된 시간

이 성립된다.

 

그래서 시작을 맨마지막 작업에 해당하는 노드부터 시작해서 백트래킹으로 각 작업의 선행시간을 포함한 작업시간들을 구했다. DFS코드보면 앞서 말한것처럼 자식들의 작업시간들 중 가장 큰값을 구하고, 그걸 자신의 작업시간에 더해서 dp에 업데이트한 후 리턴한다. 이미 구한걸 또 구할필요는 없으니 반드시 dp테이블에 업데이트하자.

 

그리고 한가지 더 유의할 점은, 맨 마지막작업에 해당하는 노드가 여러개일 수도 있다는 것을 명심하자.

즉 한덩어리의 그래프가 주어지는게 아니라 작더라도 여러덩어리가 주어지는 경우가 있다.

그렇기 때문에 각각의 그래프덩어리들에 대해서 작업시간을 구한 후, 그 중 최대값을 출력해야 한다.

이것또한 마찬가지인 이유로, 결국 모든 작업이 완료되려면 가장 긴작업시간을 가진 작업이 완료될 때까지 기다릴 수 밖에 없기 때문이다.