1516 게임 개발

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

위상 정렬(Topological Sort)은 DAG(Directed Acyclic Graph), 즉 사이클이 없는 유향 그래프에서 Indegree가 0인 정점들을 하나씩 제거해 가면서 정렬하는 알고리즘이다. 위상 정렬을 이용하여 선후 관계를 고려하면서 각 건물이 완성되기까지 걸리는 최소 시간을 구할 수 있다. 스타크래프트를 예로 들자면 스타포트를 올리기 까지의 최소 테크트리는 배럭->팩토리->스타포트이고 템플러 아카이브를 올리고 싶다면 게이트웨이->사이버 네틱스 코어->시타델 오브 아둔->템플러 아카이브 순으로 지어야 한다. 이 때 한 정점 이전에 연결되어 있는 정점들이 여러개 있다면 그 중 가장 시간이 오래 걸리는 것이 최종적으로 다음 건물의 건설 시간에 영향을 주게 된다. 이를 유의하며 ans 배열을 갱신해 나갔다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int n,t[501],p,ind[501],ans[501];
vector<int> a[501];
queue<int> q;
 
void ts()
{
    while(!q.empty())
    {
        int now=q.front(); q.pop();
        for(int next : a[now])
        {
            if(ans[next]<ans[now]+t[next])
                ans[next]=ans[now]+t[next];
            if(--ind[next]==0) q.push(next);
        }
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t[i]);
        while(true)
        {
            scanf("%d",&p);
            if(p==-1) break;
            a[p].push_back(i),ind[i]++;
        }
        if(!ind[i]) ans[i]=t[i],q.push(i);
    }
    ts();
    return 0;
}