baekjoon 1005:ACM Craft

baekjoon 1005 ACM Craft

1005번 ACM Craft

접근

첫번째 풀이는 주어진 그래프를 역방향으로 구해서 앞 vertex의 건설이 끝나는 시간 중 최대를 구하여
현재 vertex의 건설이 끝나는 시간을 구하는 방식이다.
cache[i]는 i번째 건물이 건설 완료 되는 시간이다.
그런데 위상정렬을 이용한 접근이 있다고 해서 2번째 방법으로 풀어 보았다. 먼저 위상정렬을 해놓고 앞에서부터 접근하면
지금 접근하는 vertex는 앞에 있는 indegree는 이미 모두 접근된 것이 보장된다. 그래서 i번째 건물에 접근하면
이미 i번째 건물의 건설시간은 확정이 된 상태이다.
위상정렬을 하는 방법 중 dfs를 이용하여 끝나는 시간 순으로 정렬하는 것 말고 indegree = 0인 것 넣는 방법으로 했다.

코드

#include <iostream>
#include <vector>
#include <array>
using namespace std;
array<int, 1000> cache;
int dp(int x, vector<int>& time, vector<vector<int>>& adj);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin >> t;
  while(t--){
    fill(cache.begin(), cache.end(), -1);
    int n, k; cin >> n >> k;
    vector<int> time(n);
    for(int i = 0; i < n; i++){
      cin >> time[i];
    }
    vector<vector<int>> adj(n);
    for(int i = 0; i < k; i++){
      int a, b; cin >> a >> b;
      adj[b-1].push_back(a-1);
    }
    int w; cin >> w;
    cout << dp(w-1, time, adj) << "\n";
    
  }
  return 0;
}
int dp(int x, vector<int>& time, vector<vector<int>>& adj){
  if(adj[x].empty()){
    return time[x];
  }
  int& ret = cache[x];
  if(ret != -1){
    return ret;
  }
  ret = 0;
  for(int i:adj[x]){
    ret = max(ret, dp(i, time, adj)+time[x]);
  }
  return ret;
  
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin >> t;
  while(t--){
    int n, k; cin >> n >> k;
    vector<int> time(n);
    for(int i = 0; i < n; i++){
      cin >> time[i];
    }
    vector<int> result = time;
    vector<vector<int>> adj(n);
    vector<int> inDegree(n);
    for(int i = 0; i < k; i++){
      int a, b; cin >> a >> b;
      adj[a-1].push_back(b-1);
      inDegree[b-1]++;
    }
    //topological sort
    vector<int> topologicalSortResult;
    queue<int> q;
    for(int i = 0; i < n; i++){
      if(inDegree[i] == 0){
        q.push(i);
      }
    }
    while(!q.empty()){
      int x = q.front();
      q.pop();
      topologicalSortResult.push_back(x);
      for(int i:adj[x]){
        inDegree[i]--;
        if(inDegree[i] == 0){
          q.push(i);
        }
      }
    }
    int w; cin >> w;

    //앞에서 부터 점화식 적용
    for(auto i : topologicalSortResult){
      if(i == w-1){
        break;
      }
      for(auto j : adj[i]){
        result[j] = max(result[j],result[i]+time[j]);
      }
    }
    cout << result[w-1] << "\n";
    
  }
  
}

배운 점

dp, topologicalSort 구현 해보았다.