[Algorithm]Baekjoon 1516번 : 게임 개발

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

1516번: 게임 개발

 
int n, a, b;
vector<vector<int>> graph(501);
int minBuildTimes[501] = { 0 };
int inDegrees[501] = { 0 };
int buildTimes[501] = { 0 };
int edgeCount = 0;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    queue<int> q;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> buildTimes[i];
        minBuildTimes[i] = buildTimes[i];
 
        while (1)
        {
            cin >> b;
            if (b == -1) break;
 
            graph[b].push_back(i);
            ++inDegrees[i];
            ++edgeCount;
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        if (inDegrees[i] == 0)
        {
            q.push(i);
        }
    }
 
    for (int i = 0; i < edgeCount; ++i)
    {
        if (q.empty()) break;
 
        int node = q.front();
        q.pop();
 
        for (int j = 0; j < graph[node].size(); ++j)
        {
            int nextNode = graph[node][j];
 
            minBuildTimes[nextNode] = max(minBuildTimes[nextNode], minBuildTimes[node] + buildTimes[nextNode]);
 
            if (--inDegrees[nextNode] == 0)
            {
                q.push(nextNode);
            }
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        cout << minBuildTimes[i] << endl;
    }
}
 
 
 

 

이전에 풀었던 AMC Craft 문제와 아예 같은 문제라 봐도된다. 위상정렬 문제이며, 유의해야할 점으로는

특정건물을 건설하기 전에 우선적으로 건설해야하는 건물이 한개가 아니라 여러개일 수 있다는 것이다.

즉 

1->2

1->3

2->4

3->4

 

의 그래프형태를 띄고 있을 경우, 4번건물의 최소건설시간은 2번과 3번중 건설시간이 가장 큰 값이다.

작은 값이 아니다. 왜? 2,3번 둘다 건설완료가 되어야 4번을 건설할 수 있기 때문이다.

2번이 건설시간 1초여도 3번건설시간이 10000초면 10000초를 기다려야한다.