[9] [Class 5] - 2056 작업

www.acmicpc.net/problem/2056

2056번: 작업

 

작업의 우선순위를 두어

처음에는 지나가는 시간을 1씩 올려서 하려고 했는데

그러다보니 큐에 있는 것들이 시간이 다 됐는지를 체크하는게 너무 이상한것 같아서 그만뒀고

 

먼저 기본 정석이 되는 위상정렬 그래프 구조에서

A를 indegree가 0이 된 작업, B를 A가 끝난 다음에 할 수 있는 작업이라고 생각하면

A가 끝났을 때, B가 걸리는 총 시간 = max(B의 총시간, A가 끝나는 시간 + B가 걸리는 시간) 으로 두면

B를 수행하기 위해 필요한 모든 A들에 대해서, 각각 끝나는 시간 중 제일 늦은 시간을 반영할 수 있으므로 

전체 pop하는 대상 N에, 그에 의존하는 대상의 갯수 (최대 N/2) 총 O(N * N / 2) 의 복잡도로 수행할 수 있다.

 

// https://www.acmicpc.net/problem/2056
// 위상 정렬

#include <bits/stdc++.h>

using namespace std;

vector<int> graph[10001];

int indegree[10001];
int each_time[10001];
int total_time[10001];

queue<int> q;

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

  int N; cin >> N;

  for(int i = 1 ; i <= N ; i++){
    int a,b; cin >> a >> b;
    each_time[i] = a; 
    indegree[i] = b; // 앞의 요구사항이 몇개인지 파악하기
    for(int j = 0 ; j < b ; j++){
      int c; cin >> c;
      graph[c].push_back(i); // graph[c] 는 c를 필요로 하는 녀석들의 모임
    }
  }

  // 내가 필요로 하는 애들이 언제 끝났는지는 total_time 에서 말해줄 것이다.
  // 필요로 하는 애들이 끝날 때 마다 현재 total_time와 필요로 하는 애 total_time + 내꺼 끝나는데 필요한 시간을 비교한다

  for(int i = 1 ; i <= N ; i++){
    if(indegree[i] == 0) q.push(i); // 일단 indegree가 0인 애들을 모두 넣는다
    total_time[i] = each_time[i];
  }

  while(!q.empty()){
    int now = q.front(); // indegree가 0인 애를 하나 뺀다
    q.pop();

    for(int i = 0 ; i < graph[now].size(); i++){ // now를 필요로 하는 애들에 대해서 
      int target = graph[now][i]; // 필요로 하는 애를 target이라고 하면 
      total_time[target] = max(total_time[target], total_time[now] + each_time[target]); // target의 start time은
      indegree[target] -= 1;
      if(indegree[target] == 0) q.push(target);
    }
  }

  int maxVal = 0;
  for(int i = 1 ; i <= N ; i++){
    if(maxVal < total_time[i]) maxVal = total_time[i];
  }

  cout << maxVal;

  return 0;
}