[C/C++] 백준 #1516 게임 개발(위상 정렬)

게임 개발 문제는 위상정렬(Topology sort)를 사용해서 풀 수 있는 문제입니다.

 

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

1516번: 게임 개발

 

건물을 짓기 위해서 필요한 건물이 있게 되는데요.  이 필요한 건물을 위상으로 생각하면 됩니다.

건물을 짓는데 걸리는 시간이 있는데, 이것은 여러개의 입력 간선이 있다면, 그 입력 간선중 가장 긴 시간이 소요된 것으로 시간을 적으면 되죠.

 

위상 정렬(Topology sort)

기존의 위상정렬이 순서대로 나열하는 것이었다면, 여기서는 입력 간선의 노드값에 따라서 현재의 노드값을 업데이트를 하는 부분만 추가하면 됩니다.

 

다음은 제가 작성한 코드입니다.  참조용으로만 봐주세요.

//----------------------------------------------------------------------------------------
//    baekjoon #1516 - Game development
//        - by Aubrey Choi
//        - created at 2019-11-26
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <vector>
#include <queue>

int main()
{
    int i, n, s; static int v[500], c[500], t[500];
    std::vector<int> e[500]; std::queue<int> q;
    scanf("%d", &n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&t[i]);
        while(scanf("%d",&s) && s!=-1) e[s-1].push_back(i),c[i]++;
    }
    for(i=0;i<n;i++) if(!c[i]) q.push(i);
    while(!q.empty())
    {
        s=q.front(); q.pop();
        v[s]+=t[s];
        for(auto k:e[s]) { if(v[k]<v[s]) v[k]=v[s]; if(!(--c[k])) q.push(k); }
    }
    for(i=0;i<n;i++) printf("%d\n", v[i]);
}