[백준 1516번] 게임 개발

문제 링크: https://www.acmicpc.net/problem/1516

1516번: 게임 개발

<문제 풀이> 위상 정렬, 다이나믹 프로그래밍

기본적인 위상정렬 알고리즘으로 최단거리를 갱신하면 되는데 주의할 점이 하나 있습니다.

 

indegree가 0이 되는 건물을 큐에 삽입하면서 최단거리를 갱신할 때 바로 직전 노드로만 판단하면 안 됩니다.

 

 

위와 같은 상황에서 1번 정점을 처리하고 2번 정점을 처리할 때 3번 정점의 indegree가 0이 되어서 3번 정점을 큐에 넣고 바로 직전 노드인 2번 정점으로 최단거리를 갱신하면 올바른 답인 24 가 나오지만

 

위와 같은 상황에서는 1번 정점을 고려하지 않기 때문에 24가 아닌 14가 나오게 됩니다.

 

1번 정점과 2번 정점 모두 건설이 완료되어야 3번 정점을 건설할 수 있으므로,

3번 정점을 건설하는데 걸리는 시간은 

(1번 정점과 2번 정점 중 건설이 가장 오래 걸리는 정점의 건설 시간 + 3번 정점의 건설 시간)이 됩니다

=dist[v] = max(dist[v], dist[u] + takeTime[v]);

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
 
using namespace std;
 
int n;
vector<int> adj[501];
int indegree[501];
int dist[501];
int takeTime[501];
 
void bfs() {
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            Q.push(i);
            dist[i] = takeTime[i];
        }
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (auto& v : adj[u]) {
            dist[v] = max(dist[v], dist[u] + takeTime[v]);
            indegree[v]--;
            if (indegree[v] == 0) {
                Q.push(v);
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int v = 1; v <= n; v++) {
        int t;
        cin >> t;
        takeTime[v] = t;
        while (true) {
            int u;
            cin >> u;
            if (u == -1) break;
            
            adj[u].push_back(v);
            indegree[v]++;
        }
    }
    bfs();
   
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << '\n';
    }
    return 0;
}