게임 개발 1516

문제

접근 방법

건물을 순서대로 지어야 하는데 동시에 지어도 되고 최소한의 시간으로 짓는 것을 목표로 한다.
선행으로 지어야 하는 건물이 있다면 그 건물을 지어야 하고 그것이 반복될 수 있다. (A건물의 선행이 B인데 B건물의 선행이 C라면 C를 짓고 B를 짓고 A를 지어야 한다)
위상정렬을 사용하면 순서를 보장받을 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, time, end;
    cin >> N;
    vector<int> inDegree(N + 1), timeV(N + 1), ret(N + 1);
    vector<vector<int>> graph(N + 1, vector<int>());
    queue<int> q;
    for (int i = 1; i <= N; ++i)
    {
        cin >> time;
        timeV[i] = time;
        ret[i] = time;
        while (true)
        {
            cin >> end;
            if (end == -1)
                break;
            ++inDegree[i];
            graph[end].push_back(i);
        }
    }
    for (int i = 1; i <= N; ++i)
    {
        if (!inDegree[i])
            q.push(i);
    }
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int next : graph[cur])
        {
            ret[next] = max(ret[next], ret[cur] + timeV[next]);
            if (!(--inDegree[next]))
            {
                q.push(next);
            }
        }
    }
    for (int i = 1; i <= N; ++i)
        cout << ret[i] << "\n";
    return 0;
}

풀이

위상 정렬을 통해 진입차수가 0인 것을 순서대로 해결해준다. 그러면서 시간을 갱신해주는데 선행으로 지어야 하는 건물 중 가장 오래 걸리는 시간을 기준으로 갱신해주면 된다.
진입차수가 0인 경우에만 시간을 갱신하면 문제가 발생하는데 다른 선행으로 지어야 하는 건물이 아무리 오래 걸리더라도 진입차수가 0인 조건에 걸리지 않는다면 고려되지 않기 때문이다.