[백준] 1516 - 게임 개발

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

 

알고리즘

다이나믹 프로그래밍 / 그래프 이론 / 위상 정렬 / 방향 비순환 그래프

 

설명

예 ~ 전에 풀려다가 못 풀었었는데, 오랫만에 보니까 금방 풀었다.

문제 내용부터 '나 위상 정렬' 이라고 말하고 있기 때문에, 그냥 위상 정렬 후 소요 시간만 잘 계산하여 주면 된다.

 

[각 작업에 대한 최소 소요 시간] = [입력 간선으로 들어오는 노드들 중, 가장 늦게 끝나는(최대 소요 시간)] + [해당 노드의 작업 시간]

위상 정렬

 

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int cost[501];
int result[501];    //각 건물을 짓는데 필요한 시간
int in[501];
vector<int> graph[501];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        cin >> cost[i];
        int a;
        while (true) {
            cin >> a;
            if (a == -1)break;
            graph[a].push_back(i);
            in[i]++;
        }
    }
    
    queue<int> q;
    for (int i = 1; i <= N; ++i)
    {
        if (in[i] > 0) continue;
        in[i]--;
        q.push(i);
        result[i] = cost[i];
    }
    while (!q.empty())
    {
        int qSize = q.size();
        for (int i = 0; i < qSize; ++i)
        {
            int now = q.front();
            //cout << now << " ";
            q.pop();
            for (int k = 0; k < graph[now].size(); ++k)
            {
                int nxt = graph[now][k];
                in[nxt]--;
                result[nxt] = max(result[nxt], result[now]);
                if (in[nxt] == 0) {
                    q.push(nxt);
                    result[nxt] += cost[nxt];
                }
            }
        }
    }
    for (int i = 1; i <= N; ++i) cout << result[i] << "\n";
    return 0;
}