(골드 4, C++) 백준 2056: 작업

문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

입력

첫째 줄에 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, ..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

출력

첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

---

핵심

• 정점을 수를 입력 받고 정점마다 선행되어야하는 업무를 입력 받는다.
• 선행 업무가 없는 여러개의 업무는 병렬 처리될 수 있다.
• 업무가 끝날 수 있는 최소의 시간을 출력한다. 

---

코드

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <sstream>
using namespace std;

typedef pair<int, int> pii;

int indegree[10001];

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;

    int result = 0;
    vector<int> edge[10001];
    int time[10001];
    for (int i = 1; i <= n; i++)
    {
        int temp;
        cin >> time[i] >> temp;

        for (int j = 0; j < temp; j++)
        {
            int node;
            cin >> node;

            edge[i].push_back(node);
        }

        int _max = 0;
        for (auto ele : edge[i])
        {
            _max = max(time[ele], _max);
        }

        time[i] += _max;
        result = max(time[i], result);
    }

    cout << result;

    return 0;
}

---

풀이

이번 문제는 위상정렬을 이용해 풀이하는 문제이다.

이전에 학습한 Kahn's Algorithm을 사용하려다가 꼬여서 시간이 좀 걸렸다..

https://qktjwl123.tistory.com/144

알고리즘: 위상정렬 (Kahn's Algorithm)

 

선행되어야하는 업무의 넘버가 현재 업무의 넘버보다 반드시 작다는 조건 덕분에 DP와 위상정렬을 이용하면 쉽게 풀이할 수 있는 문제이다.

 

1. 정점의 수를 입력받는다.
2. 업무에 걸리는 시간과 선행되어야하는 업무를 입력 받는다.
3. 선행되어야하는 업무 중 제일 늦게 끝나는 업무 + 현재의 업무가 끝나는 시간을 time배열에 기록한다.
4. time 배열에 있는 수 중 제일 큰 수를 출력한다. 

---

시간 복잡도

n번 반복하는 반복 문에서 간선의 수만큼 e번 반복하는 반복문이 두개 있다.

따라서 시간 복잡도는 O(n+e)이다.

 

문제의 입력 조건에서 최대 정점은 10000이고 간선은 최대 1+2+ ... 9999개이므로,

최대 50005000번 연산을 하고 1억번 연산에 1초가 소요된다는 평균 값을 대입하면 최악의 경우 500ms이 걸린다.

 

실제 풀이에는 72ms가 소요되었다.