[BOJ] 2056번 - 작업

백준 2056번 - 작업

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	5380	2327	1658	40.878%

문제

수행해야 할 작업 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)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

 

출력

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

---

예제 입력 1

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

23

•  1번 작업 : 0~5  2번 작업 : 5~6
•  3번 작업 : 6~9  4번 작업 : 5~11
•  5번 작업 : 11~12 6번 작업 : 11~19
•  7번 작업 : 19~23

출처

www.acmicpc.net/problem/2056

2056번: 작업

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 위상 정렬

접근 방법

작업들이 주어지고, 선행 관계가 있는 작업들은 먼저 수행해야하는 작업을 처리한 다음 처리가 가능하다.

i번째 작업을 처리 하는데 걸리는 시간 배열을 answer[i] 라고 정의하면 우리가 원하는 정답은 모든 작업 중 가장 늦게 끝나는 작업이 곧 모든 작업이 끝나는 최소 시간이 된다.

 

각 작업들을 그래프의 노드로 표현했을 때, 하나의 노드가 가지는 정보는 3가지 이다.

첫번째는 해당 노드가 가지는 가중치, 나머지는 해당 노드로 들어오는 정점들의 집합, 해당 노드로 부터 출발해서 도달할 수 있는 정점들의 집합이다.

 

특정 작업 k를 처리하기 이전에 ${N_i}$작업들을 수행해야 한다면, 특정 작업 k 를 처리한 후의 시간 {max(N_j), 1<=j<=n} + k를 처리하기 위해 걸리는 시간 일 것이다. 

 

단순하게 생각해보자.

지금 당장 처리할 수 있는 작업은 선행관계에서 최상위에 존재하는 작업일 것이다. 그래프로 표현하였을 때, in-coming edge가 존재하지 않는 노드이다. 지금 당장 처리할 수 있는 작업을 수행하고 나면, 해당 작업 이후에만 할 수 있는 다른 작업들을 수행할 수 있는 상태가 될 것이다. 

그러면, 우리가 구현해야 하는 부분은 다음과 같다.

 

1. in-coming 노드가 하나도 없는 노드 먼저 처리한다.

2. 해당 노드와 연결 되는 모든 edge들을 끊어 준다.

3. 해당 작업이 끝났을 때의 시간을 answer배열에 저장한다. 그러면 이 후 작업을 처리하는데에는 (이전 작업이 끝난 시간 + 현재 작업을 처리하는데 소요되는 시간) 이 될 것이다.

 

이러한 과정을 그래프에 존재하는 모든 정점들에 대해 수행한다면 올바른 정답을 구할 수 있을 것이다.

 

이러한 그래프에 존재하는 노드 간의 위상을 정렬하는 것을 Topological Sort라고 한다.

 

* 주의해야 할 점

처음 문제를 풀었을 때 간과하고 있던 부분이 있었다. 각 노드가 가지는 가중치가 각기 다르기 때문에 마지막에 지우는 노드 또한 중요하다.

특정 작업을 마친 시간 = (이전 작업이 끝난 시간 + 현재 작업을 처리하는데 걸리는 시간) 이다. 

다음과 같은 경우를 살펴보자

괄호 : 가중치

여기서 1번 노드를 먼저 지워버릴 경우, 결론적으로 3번 작업이 끝나는 시점은 2번 작업을 처리 한 후 시간 + 3번 작업을 처리하는데 걸리는 시간이 될 것이다. 단순하게 in-coming edge의 개수를 0으로 만드는 바로 이전 작업이 특정 작업이 끝난 후의 최적시간을 보장해 주진 않는다는 뜻이다. 

특정 작업 k를 처리하기 이전에 ${N_i}$작업들을 수행해야 한다면, 특정 작업 k 를 처리하는데 걸리는 시간은 ${min(N_j), 1<=j<=n}$ 일 것이다.

최적해를 구하기 위해서 가장 빠르게 끝나는 작업을 먼저 처리해줘야하는 로직이 필요하다! 

필자는 단순하게 priority queue를 통해 현재 처리할 수 있는 작업 중에서 가장 빠르게 처리할 수 있는 일 부터 처리해주므로서 결론적으로 특정 작업을 하기 이전에 수행해야 할 선행 작업들 중 가장 늦게 끝나는 일의 시간이 그 다음 작업을 할 수 있게 되는 올바른 시간이 되도록 만들어 주었다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int cost;
    vector<int> in, out; // 선행되는 정점(in), 이 후 정점(out)
};
vector<int> answer;
vector<Node> nodes;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int N; // 수행해야 할 작업
    cin >> N;
    answer.resize(N+1);
    nodes.resize(N+1);

    // in-edge, out-edge!!
    for(int i=1; i<=N; i++){
        int cost, precedence_cnt;
        cin >> cost >> precedence_cnt;

        nodes[i].cost = cost;

        while(precedence_cnt--){
            int precedence_vertex;
            cin >> precedence_vertex;

            nodes[i].in.push_back(precedence_vertex);
            nodes[precedence_vertex].out.push_back(i);
        }
    }

    // <주의> in-edge가 0인 정점들을 제거할 때 cost가 작은 것을 먼저 지워야한다!!
    // 그냥 priority queue로 구현해보자.

    // PQ 의 원소 -> (cost, 정점)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> PQ;
    for(int i=1; i<=N; i++){
        if( nodes[i].in.empty() ){
            PQ.push({nodes[i].cost, i});
            answer[i] = nodes[i].cost;
        }
    }

    while(!PQ.empty()){
        // Cycle이 존재하는 그래프는 주어지지 않는다.
        pair<int,int> top = PQ.top(); PQ.pop();
        // 해당 정점과 연결 되어 있는 간선들을 모두 끊는다.
        int current_vertex = top.second;

        // 해당 노드들은 current_vertex 로 부터 들어오는 in-edge가 없어진다.
        vector<int> hasToErase;
        for(auto item : nodes[current_vertex].out)
            hasToErase.push_back(item);

        for(int i=0; i<hasToErase.size(); i++){
            int target_vertex = hasToErase[i];
            // target의 in-edge중 current_vertex를 지운다.
            for(auto iter = nodes[target_vertex].in.begin(); iter != nodes[target_vertex].in.end(); iter++){
                if( *iter == current_vertex){
                    nodes[target_vertex].in.erase(iter);
                    break;
                }
            }
            if( nodes[target_vertex].in.empty() ){
                answer[target_vertex] = answer[current_vertex] + nodes[target_vertex].cost;
                PQ.push({answer[target_vertex], target_vertex});
            }
        }
    }

    int min_time = 0;
    for(int i=1; i<=N; i++){
        if( min_time < answer[i] )
            min_time = answer[i];
    }
    cout << min_time;

    return 0;
}

 

2번 째 방법

문제의 의도에는 맞지 않는 방법이지만 최적해를 구할 수 있는 방법이 있다.

#include<stdio.h>
int time[10005];
int d[10005];
int n,ans;
int max(int a,int b){return a>b?a:b;}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int cnt;
		scanf("%d %d",&time[i],&cnt);
		for(int j=1;j<=cnt;j++){
			int in;
			scanf("%d",&in);
			d[i]=max(d[i],d[in]);
		}
		d[i]+=time[i];
		ans=max(ans,d[i]);
	}
	printf("%d",ans);
	return 0;
}

매 작업을 처리할 수 있는 시간을 d라고 정의하였고, 해당 작업을 처리하는데 걸리는 시간을 time으로 두었다.

논리는 위에서 설명한 바와 같다.