[백준] 2056번 작업 C++ 코드

코드

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

using namespace std;

int n;
int timetable[10003], indegree[10003], result[10003];
vector<int> adj[10003];

int main() {
    cin >> n;
    
    // 입력 처리
    for (int i = 1; i <= n; ++i) {
        int time, count;
        cin >> time >> count;
        timetable[i] = time; // 작업에 걸리는 시간 저장
        for (int j = 0; j < count; ++j) {
            int pre_task;
            cin >> pre_task;
            adj[pre_task].push_back(i); // 선행 작업 관계 설정
            indegree[i]++; // 해당 작업의 선행 작업 개수 증가
        }
    }
    
    queue<int> q;
    
    // 초기 선행 작업이 없는 작업들을 큐에 삽입
    for (int i = 1; i <= n; ++i) {
        if (indegree[i] == 0) {
            q.push(i);
            result[i] = timetable[i]; // 선행 작업이 없으면 바로 완료 가능
        }
    }
    
    // 위상 정렬 알고리즘 수행
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        
        for (int next : adj[current]) {
            indegree[next]--;
            // 해당 작업의 완료 시간 갱신
            result[next] = max(result[next], result[current] + timetable[next]);
            if (indegree[next] == 0) {
                q.push(next);
            }
        }
    }
    
    // 모든 작업 중 가장 늦게 끝나는 시간을 출력
    int answer = 0;
    for (int i = 1; i <= n; ++i) {
        answer = max(answer, result[i]);
    }
    
    cout << answer << endl;
    return 0;
}

풀이

선행관계가 있는 문제이므로, 위상정렬 알고리즘을 사용했다. 처음에 indegree가 0이 될 때 시간을 계산해서 잘못된 답을 얻었다. 이 문제는 여러 선행 작업이 존재하기 때문에, 가장 늦게 완료되는 선행 작업을 반영해야 한다. 따라서 완료 시간을 매번 최대값을 기준으로 갱신해야 정확한결과를 얻을 수 있다.

 

이를테면, 작업 i가 여거 선행 작업을 가지고 있다면, 가장 늦게 끝나는 선행이 작업이 언제 끝나는지를 기준으로 작업 i의 완료 시간이 결정된다. 이때, 모든 선행 작업이 완료되지 않은 상태라 할지라도 어느 선행 작업이 가장 늦게 끝나는지 미리 계산해 두어야 한다. 후속 작업의 예상 완료 시간은 현재까지 계산된 선행 작업 중 가장 늦게 끝나는 작업의 시간을 반영해야 하기 때문에, 선행 작업이 완전히 끝나기 전에라도 중간 중간에 후속 작업의 시간을 갱신할 필요가 있다.

 

선행 작업이 하나만 있는 경우는 상관없지만, 여러 개일 경우에는 그 중에서 가장 늦게 끝나는 작업의 시간을 반영해야 후속 작업의 완료 시간을 정확히 계산할 수 있다.