백준 1516번 게임 개발[C++]

1. 문제 풀이

1-1. 문제 개요

안녕하세요. 오늘 풀어볼 문제는 백준 1516번 게임 개발입니다. 문제의 유형은 topological sorting(위상 정렬)을 사용한 dynamic programming 응용이었습니다.

 

 이 문제는 위상 정렬을 통해 정점들을 나열하면서 하는 문제입니다. topological sorting과 dynamic programming을 모른다면 이 문제를 푸는 것은 어렵습니다. 이런 알고리즘 기법들에 대해서 공부를 하시고, 기초와 응용문제들을 몇 개 풀어보시고 도전하는 것을 추천드립니다.

 

1-2. 풀이 원리

문제에서 제공한 예제 입력을 그래프로 표현을 해보면 아래와 같습니다.

 위상 정렬 알고리즘의 원리를 따라가게되면 indegree가 없는 vertex를 찾아서 시작을 합니다. 위 그래프에서 indegree가 없는 정점은 1이고 건설 시간이 10이므로 dp table에 10을 채워놓고 시작하면 되겠습니다.

1번 vertex의 outdegree로 이동할 수 있는 vertex들을 순회하면서 각 vertex의 indegree 개수를 1씩 감소시키고 dp table의 값이 최댓값을 갖도록 갱신해 주고 감소된 indegree가 0인 vertex를 queue에 삽입하면서 진행하면 풀이가 가능합니다.

이 후 상황에 대해서는 그림으로 나열해 보겠습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb;
#define X first
#define Y second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const char nl = '\n';
int n, t[505], deg[505], ans[505];
vi adj[505];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for(int cur = 1; cur <= n; cur++){
    cin >> t[cur];
    int prv;
    while(cin >> prv, prv != -1){
      adj[prv].pb(cur);
      deg[cur]++;
    }
  }
  queue<int> q;
  for(int i = 1; i <= n; i++){
    if(deg[i]) continue;
    ans[i] = t[i];
    q.push(i);
  }
  while(!q.empty()){
    auto cur = q.front(); q.pop();
    for(auto nxt : adj[cur]){
      ans[nxt] = max(ans[nxt], t[nxt] + ans[cur]);
      if(--deg[nxt] == 0){
        q.push(nxt);
      }
    }
  }
  for(int i = 1; i <= n; i++) cout << ans[i] << nl;
}

 

3. 제출 결과