[백준 / BOJ] C++ 1516 게임 개발

1516번: 게임 개발

 

문제

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

1516번: 게임 개발

 

 

풀이

각 건물을 짓는 데는 먼저 지어져야 하는 건물이 있으므로 위상 정렬을 해야 한다. 그리고 각 건물이 완성되기까지 걸리는 최소 시간을 출력해야 하므로 위상 정렬하는 순서에 따라 시간을 계산해 주면 된다.

 

위상 정렬은 큐에 들어가고 나오는 순서대가 정렬된 순서이므로 차례대로 작업을 수행한다. 기본적으로 각 건물을 완성하는 데 걸리는 시간은 그 건물을 완성하는 시간이다. 하지만 앞서 완성해야 하는 건물이 완성된 후에 건설을 시작할 수 있는 건물들은 앞선 건물의 완성시간의 최댓값 + 현재 건물을 완성하는 데 걸리는 시간이 최댓값이 된다. 따라서 front로 나온 원소를 현재 노드라고 하면 현재 노드에서 나아갈 수 있는 다음 노드들에 대해 다음 노드를 완성하는 데 걸리는 시간 ans[next] = max(ans[next], ans[node] + cost[next])가 된다. 나가는 정점이 없는 노드들은 무시되어 처음 그 건물을 완성하는 데 걸리는 시간이 답이 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N;
  vector<int> edge[32001], inDegree(32001, 0), cost(32001), ans;
  cin >> N;
  for (int i = 1; i <= N; i++) {
    cin >> cost[i];
    while (1) {
      int x;
      cin >> x;
      if (x == -1)
        break;
      inDegree[i]++;
      edge[x].push_back(i);
    }
  }
  queue<int> q;
  for (int i = 1; i <= N; i++)
    if (inDegree[i] == 0)
      q.push(i);
  ans = cost;
  for (int i = 1; i <= N; i++) {
    int node = q.front();
    q.pop();
    for (int next : edge[node]) {
      ans[next] = max(ans[next], ans[node] + cost[next]);
      if (--inDegree[next] == 0)
        q.push(next);
    }
  }
  for (int i = 1; i <= N; i++)
    cout << ans[i] << '\n';
  return 0;
}