[백준 2056] 작업

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

 

1. 문제 이해

첫째줄에 수행 작업 N이 주어진다.

2~N+1줄까지 '각 작업의 시간, 선행할 작업들 개수, 선행 관계에 있는 작업들의 번호'가 주어지면,

모든 작업을 완료하기 위해 필요한 최소시간을 구하면 된다.

 

2. 조건

- k번 작업에 대해, 선행 관계에 있는 작업 번호는 1 ~ (k-1)이하임.

- 선행 관계 없는 작업도 존재함(1번 작업은 항상) = 선행작업 0

 

3. 풀이

선행 작업이기 때문에 사이클이 존재하지 않고, 최소시간을 구하는 문제이기 때문에 위상 정렬로 코드를 짰다.

입력이 다음과 같이 주어졌다. 

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

 

이를 이해하고자 다음과 같이 정리 해보았다.

1번 작업 : 5시간, 선행 0 

2번 작업 : 1시간, 선행 1 - 1번

3번 작업 : 3시간, 선행 1 - 2번

4번 작업 : 6시간, 선행 1 - 1번

5번 작업 : 1시간, 선행 2 - 2, 4번

6번 작업 : 8시간, 선행 2 - 2, 4번

7번 작업 : 4시간, 선행 3 - 3, 5, 6번

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

vector<int> edge[10003];
int in_degree[100003];
int t[100003];

int main() {
    int n, k, t_input, oper, result = 0; // t_input: 시간
    priority_queue<pair<int, int>> pq;

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> t_input >> k;
        t[i] = t_input;

        if (k == 0) {
            pq.push({-t_input, i});
        } else {
            while (k--) {
                cin >> oper;
                edge[oper].push_back(i);
                in_degree[i]++;
            }
        }
    }

    while (!pq.empty()) {
        int op_time = -pq.top().first;
        int num = pq.top().second;
        pq.pop();

        result = max(op_time, result);

        for (int next: edge[num]) {
            in_degree[next]--;
            if (!in_degree[next]) {
                int op = op_time + t[next];
                pq.push({-op, next});
            }
        }
    }

    cout << result;

    return 0;
}

 

 

4. 구현/디버깅 => 반례찾음

7
5 0
3 0
6 0
1 0
8 0
4 0
2 0
8(정답)

 

=> max 값이 나오지 않아 추가해줌