백준(BOJ) 1005 : ACM Craft

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

1005번: ACM Craft

 

 

작업의 우선순위가 주어지고 특정 작업을 수행하기 위해서는 그 작업보다 먼저 수행되어야하는 작업들이 모두 완료되어야한다.

이 문제와 마찬가지로 위상 정렬 문제라는 것을 알 수 있다.

 

하지만 이 문제는 특정 건물을 지을 수 있는 시간을 묻는 것이므로 단순 위상정렬 뿐만이 아닌 구현이 필요하다.

 

이 그림을 확인해 보자.

건물 1의 경우 10초가 소요 될 것이다.

건물 2와 3의 경우에는 각각 11초, 110초가 소요된다. (건물 1이 완료되어야 하기 때문이다.)

마지막으로 건물4의 경우에는 120초가 소요된다.

 

위에서 찾을 수 있는 것은 무엇일까?

작업을 완료하려는 건물의 소요시간은 그 이전에 수행해야했던 건물들 중 가장 오래 걸리는 시간이 소요되는 건물의 시간을 더해준 값이라는 것이다!

 

큐에 들어있는 작업의 경우, 이제 수행이 가능한 작업이라는 의미이므로 그 전까지 만났던 작업들 중 가장 최댓값을 더해주는 것으로 해결할 수 있다.

 

아래는 소스코드이다.

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 987654321;

int N, M, T;
int tim[1001] = {};
int buildtime[1001] = {}; 
int degree[1001] = {};
vector<vector<int> > adj(1001);

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

  while(T--) {
    int N, K, want;
    cin >> N >> K;
    memset(tim, 0, sizeof(tim));
    memset(buildtime, 0, sizeof(buildtime));
    memset(degree, 0, sizeof(degree));
    adj = vector<vector<int> >(1001);
    queue<int> q;

    for(int i = 1 ; i <= N ; i++) {
      cin >> buildtime[i];
    }
    for(int i = 0 ; i < K ; i++) {
      int a, b;
      cin >> a >> b;
      adj[a].pb(b);
      degree[b]++;
    }

    for(int i = 1 ; i<= N ; i++) {
      if(degree[i] == 0) q.push(i);
    }
    cin >> want;
    vector<vector<int> > tmp(1001);

    for(int i = 1 ; i <= N ; i++) {
      int cur = q.front();
      q.pop();
      tim[cur] = buildtime[cur];
      for(int j = 0 ; j < tmp[cur].size() ; j++) {
        tim[cur] = max(tim[cur], tim[tmp[cur][j]] + buildtime[cur]);
      }
      for(int j = 0 ; j < adj[cur].size() ; j++) {
        int nxt = adj[cur][j];
        tmp[nxt].pb(cur);
        degree[nxt]--;
        if(degree[nxt] == 0) {
          q.push(nxt);
        }
      }
    }
    cout << tim[want] << endl;
  }
}