[C++] 백준 2056: 작업

문제 이해

- N: 수행해야 할 작업의 개수 (3 ~ 10,000, 10^4)

- 각각의 작업마다 걸리는 시간 (1 ~100, 10 ^ 2)

 

- 작업 간에는 선행 관계가 존재

- 선행 관계가 없을경우, 동시에 수행이 가능하다.

 

<입력>

- 각 줄 처음: 각 작업을 하는데 걸리는 시간

- 각 줄 두 번째: 선행 관계의 개수

- 나머지: 선행 관계 작업들의 번호

 

<출력>

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

 

 

문제 풀이

선행 관계, 즉 순서가 주어진 그래프에서 전체 순서를 구하는 문제이다.

 

역시 위상 정렬을 사용하면 쉽게 풀 수 있을거 같다!

 

 

특징적인 점은 선행 관계가 없을경우 동시에 수행이 가능하다는 것이다.

모든 작업을 완료하기 위한 최소 시간을 구하는데 동시에 수행이 가능하다?

=> DP를 사용하면 해결할 수 있다.

 

dp[i] = i번째 작업을 하는데 걸리는 최소 시간

 

1. 입력

cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>cost[i];
        dp[i] = cost[i];

        int cnt;
        cin>>cnt;
        for(int t = 0; t < cnt; t++){
            int prev;
            cin>>prev;
            v[prev].push_back(i);
            inDegree[i]++;
        }
    }

각 dp의 값들은 각 작업의 소요시간으로 초기화 해주자.

 

헷갈리면 안 되는 점은 마지막으로 입력받는 값들은 작업 전에 되어있어야 할 선행 작업이라는 점이다.

 

 

2. 위상정렬

//위상정렬
    for(int i = 1; i <= n; i++){
        if(inDegree[i] == 0){
            q.push(i);
        }
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();

        int size = v[now].size();
        for(int i = 0; i < size; i++){
            int next = v[now][i];
            dp[next] = max(dp[next], dp[now] + cost[next]);

            inDegree[next]--;
            if(inDegree[next] == 0){
                q.push(next);
                
            }
        }
    }

dp 값을 초기화 하는 과정에서 max를 쓰는 게 의아할 수 있지만,

이미 위상정렬을 통해 각 순서는 최적으로 만들고 있다.

 

선행되어야 할 작업 중에서,

동시에 수행하는 작업 중 나중에 끝나는 것이 끝나고 나서 다음 작업이 수행되어야 하므로

max를 사용해서 초기화해줘야 한다.

 

 

dp[next] = max(dp[next], dp[now] + cost[next]);

위의 초기화 수식의 코드 위치도 중요하다고 생각하는데

필자는 처음에는 inDegree[i] == 0 일때만 초기화를 해줘야 한다고 생각했다.

 

하지만, 예시를 통해 반례를 쉽게 찾을 수 있다.

3

10 0

4 0

1 2 1 2

라는 예제가 있을 때

 

dp 배열의 값은

10 4 11 이 되어야 한다.

 

하지만, 만약  inDegree[i] == 0 일때만 초기화를 한다면

2번째 정점에서 나가는 간선을 없앨 때 초기화를 하므로 dp[3] = 5가 될 것이다.

이렇게 초기화를 언제 하는지도 잘 생각해서 해야했던 문제이다.

 

 

전체 코드

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

int n;
vector<int> v[10005];
int inDegree[10005];
queue<int> q;

int cost[10005];
int dp[10005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //입력
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>cost[i];
        dp[i] = cost[i];

        int cnt;
        cin>>cnt;
        for(int t = 0; t < cnt; t++){
            int prev;
            cin>>prev;
            v[prev].push_back(i);
            inDegree[i]++;
        }
    }

    //위상정렬
    for(int i = 1; i <= n; i++){
        if(inDegree[i] == 0){
            q.push(i);
        }
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();

        int size = v[now].size();
        for(int i = 0; i < size; i++){
            int next = v[now][i];
            dp[next] = max(dp[next], dp[now] + cost[next]);

            inDegree[next]--;
            if(inDegree[next] == 0){
                q.push(next);
                
            }
        }
    }

    int ans = 1;
    for(int i = 1; i <= n; i++){
        ans = max(ans, dp[i]);
    }
    cout<<ans;
    
    return 0;
}