[1516번] 게임 개발

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 위상 정렬 :: http://www.crocus.co.kr/716

위상 정렬을 이용하여 푸는 문제이다.

이 문제에서 생각해야 할 내용은 앞선 건물이 건설되어 자신의 건물이 건설되기 위해서는

최대 시간을 기준으로 계산하여야 한다는 것이다.

예를 들어

만약 a가 지어지기 위해 b와 c가 우선 완료되어야 하는데

b가 10초, c가 20초 걸린다면 a는 10초후에 건설할 수 있는게 아닌

c가 완료된 20초 뒤 부터 지어질 수 있는 것이다.

문제에서 각 건물이 완성되는 최소 시간을 찾아라 했지만, 

그 건물이 위상정렬에 의해 지어지는 최대 시간을 구하는 것이 곧 최소 시간을 찾는 것이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
 
vector<int> vc[501];
int line[501]; // 정점으로 들어오는 간선의 수
int result[501]; // x번째 건물 짓는데 최종 걸리는 시간
int waiting[501]; // x번째 건물 짓는데 걸리는 시간
 
int main()
{
    int n, m;
    scanf("%d", &n);
 
    // 입력 부분
    for (int i = 1; i <= n; i++)
    {
        int cur, prev;
 
        scanf("%d", &waiting[i]);
 
        cur = i;
 
        while (1)
        {
            scanf("%d", &prev);
 
            if (prev == -1)
                break;
 
            line[cur]++;
            vc[prev].push_back(cur);
        }
    }
 
    queue<int> q;
 
    // 위상 정렬을 하기 위해 line가 0인 정점은 q에 넣어준다.
    for (int i = 1; i <= n; i++)
    {
        if (line[i] == 0)
            q.push(i);
        
        // result에 자기 자신 건설 시간을 추가해준다.
        result[i] += waiting[i];
    }
 
    for (int i = 0; i < n; i++)
    {
        int cur = q.front();
        q.pop();
 
        for (int j = 0; j < vc[cur].size(); j++)
        {
            int next = vc[cur][j];
 
            // 만약 a가 지어지기 위해 b와 c가 우선 완료되어야 하는데
            // b가 10초, c가 20초 걸린다면 a는 10초후에 건설할 수 있는게 아닌
            // c가 완료된 20초 뒤 부터 지어질 수 있는 것이다.
            result[next] = max(result[next], result[cur] + waiting[next]);
 
            if (--line[next] == 0)
            {
                q.push(next);
            }
        }
 
    }
 
 
    for (int i = 1; i <= n; i++)
        printf("%d\n", result[i]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>