[백준/C++] 1516. 게임개발

게임개발

사이클이 없는 direct 그래프에서 순서를 찾는 알고리즘은 위상정렬이다. 위상정렬에서는 싸이클이 없어야한다
n번 입력을 받는데 시간, 먼저 지어져야할 건물들, 막줄표시 로 입력이 들어온다.
예를 들어 입력이 10,1,2,3,-1 이라고 한다면
10, {1,2,3}, -1 이라고 보면 된다.

위상정렬을 돌면서 현재 건물과 그 다음 건물의 시간을 더해서 더 큰 수를 저장해주면 된다. 예제입력 1을 그림으로 정리하자면 다음과 같다.

만약 비교를 해서 저장해야 할지 이해가 가지 않는다면 다음 입력을 확인해보자!

2와 4를 이어주었다. 큐에는 2가 먼저 들어오기 때문에 4의 결과시간이 24로 저장된다. 그 다음 3번건물을 계산할 때에도 4와 연결되어 있기 때문에 건물4의 result가 18로 들어온다. 하지만 시작부터 18시간 후에도 건물2번이 지어져있지 않기 때문에 건물4는 완성될 수 없다. 따라서 비교하여 더 큰 결과를 저장해주어야 한다.

*입력해보세요!
예제입력2

5
10 -1
10 1 -1
4 1 -1
4 2 3 1 -1
3 3 -1

예제출력2

10
20
14
24
17

코드는 다음과 같다!

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n;
int inDegree[501];
vector <int> v[501];
int btime[501];
int result[501] = {0, };

void topology_Sort(){
    queue <int> q;

    for(int i = 1; i<=n; i++){
        if(inDegree[i] == 0){
            q.push(i);
            result[i] = btime[i];
        }
    }

    for(int i = 1; i<=n; i++){

        if(q.empty()){
            //cycle 이 있음.
            break;
        }

        int x = q.front();
        q.pop();
        
        for(int i  = 0; i<v[x].size(); i++){
            int y = v[x][i];
            result[y] = max(result[y], result[x] + btime[y]);

            if(--inDegree[y] == 0){
                q.push(y);
            }
        }
    }
}
int main(){
    cin>>n;

    for(int i = 1; i<=n; i++){
        cin>>btime[i];

        while(true){
            int a;
            cin>>a;
            if(a == -1){
                break;
            }
            v[a].push_back(i);
            inDegree[i]++;
        }
    }

    topology_Sort();

    for(int i  = 1; i<=n; i++){
        cout<<result[i]<<endl;
    }
}