BOJ 2056

문제

작업 성공

 

2 초

256 MB

11054

5110

3656

43.215%

문제

수행해야 할 작업 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​

 

풀이

정해진 순서에 따라 작업을 시행해 그래프상 마지막 노드에 해당하는 작업을 끝내야 하는 위상정렬 문제이다.

사이클이 생기면 위상정렬이 성립될 수 없지만, 이 문제는 사이클이 안생긴다는 가정 하에 풀면 된다.(지문에 관련내용이 없기 때문)

 

우선 시간, 작업 수행 전 완료되야할 작업의 수, 작업 수행 전 완료되야할 작업 번호가 주어진다.

그러므로 이를 구조체를 통해 선언해주었다.

struct p{
    int time;
    vector<int>edges;
    int num;
};

그런데 여기서 edges 벡터에 들어가야 하는 값들은 수행 전 완료되야할 작업 번호가 아니라 이 작업 수행 후 수행될 작업에 번호가 들어가야 한다.

 

위상정렬에서는 일의 순서에 따라 간선의 방향이 잡혀야 하므로 그렇다. 

 

또한, 특정 작업에 대한 구조체를 인덱스를 통해 바로 접근할 수 있게 하기 위해 구조체 p형 벡터를 하나 선언해주었다.

vector<p>v(10001);

입력받을때 간선정보 입력받는 부분에 주의하자. 입력받은 작업에 현재 작업을 넣어주어야 한다.

for(int i=1; i<=N; i++){
        int time, s_num;
        cin>>time>>s_num;
        if(s_num == 0) q.push(i);
        v[i].time = time;
        v[i].num = s_num;
        for(int j=0; j<s_num; j++){
            int s;
            cin>>s;
            v[s].edges.push_back(i);
        }
    }

그 다음은 위상정렬을 하는 코드인데, 이 문제에서는 특정 작업이 시행되기 이전에 시간이 얼마나 걸렸나를 따로 기록해야 한다.

queue에서 맨 앞으로 가는 경우가 특정 작업이 시행되는 경우이므로 arr[q.front()] 에 그 작업이 얼마나 걸렸나를 바로 더해주고,

q.front()에 해당하는 작업이 끝난 후 시행되는 작업의 값에 q.front() 작업이 끝난 시간을 비교해서 넣어주어야 한다.

간선의 거리가 같은 작업은 동시간에 수행될 수 있기 때문에 대소비교를 통해 값을 넣어준다.

 

중요한건 v[cur].edges를 통해 보는 작업들은 무조건 현재 작업과 거리가 간선 하나밖에 안된다는 것이다.

for(int i=1; i<=N; i++){
        int cur = q.front();
        q.pop();
        arr[cur] +=  v[cur].time;
        for(auto e : v[cur].edges){
            v[e].num -= 1;
            if(v[e].num == 0)
                q.push(e);
            if(arr[e] < arr[cur]) arr[e] = arr[cur];
        }
    }

 

전체 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, arr[10001], ans;
queue<int>q;
struct p{
    int time;
    vector<int>edges;
    int num;
};
vector<p>v(10001);
int main(){
    cin>>N;
    for(int i=1; i<=N; i++){
        int time, s_num;
        cin>>time>>s_num;
        if(s_num == 0) q.push(i);
        v[i].time = time;
        v[i].num = s_num;
        for(int j=0; j<s_num; j++){
            int s;
            cin>>s;
            v[s].edges.push_back(i);
        }
    }
    for(int i=1; i<=N; i++){
        int cur = q.front();
        q.pop();
        arr[cur] +=  v[cur].time;
        for(auto e : v[cur].edges){
            v[e].num -= 1;
            if(v[e].num == 0)
                q.push(e);
            if(arr[e] < arr[cur]) arr[e] = arr[cur];
        }
    }
    for(int i=1; i<=N; i++)
        ans = max(ans, arr[i]);
    cout<<ans;

}