[ 백준 1516 ] 게임개발 (C++)

백준의 게임개발(1516) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

각 건물을 짓는데 걸리는 최소시간을 출력하는 문제이다.

건물을 짓기 위해서 우선적으로 먼저 지어야 하는 건물들고 있고 그러지 않은 건물들도 존재한다.

따라서 건물을 짓는 순서를 정하기 위해서 위상정렬을 사용해서 접근해 보았다.

위상정렬은 "일을 처리할 때, 처리할 일의 순서를 정하는 정렬" 이다.

이 문제에서 고려해 주어야 하는 것은, 각 건물이 완성되기 까지 걸리는 최소시간을 구해야 하는 것이다.

그럼 다음과 같은 경우를 생각해보자.

[ 건물번호 , 건물을 짓는데 걸리는 시간 , 이 건물을 짓기 위해 먼저 지어야 할 건물 리스트 ] 로 표현을 했을 때

[ 1 , 10 , -1 ] (건물리스트가 -1 인 것은 우선적으로 지을 건물이 없음을 표시)

[ 2 , 3 , -1 ]

[ 3 , 1 , { 1, 2 } ]

위와 같은 경우이다.

1번 건물은 건설하는데 10초가 걸리고, 우선적으로 지어야 할 건물이 없다.

2번 건물은 건설하는데 3초가 걸리고 , 우선적으로 지어야 할 건물이 없다.

3번 건물은 건설하는데 1초가 걸리고, 우선적으로 지어야 할 건물은 { 1, 2 } 번 건물이 있다.

이 때, 3번 건물을 짓는데 걸리는 시간은 몇초 일까?

눈으로 계산해보면 11초가 될 것이다. 0초에 1번 건물과 2번 건물을 동시에 지으면 3초에 2번건물은 완성, 10초에 1번건물이

완성, 그 이후에 3번 건물을 짓게되면 11초가 나오게 된다.

즉, "특정 건물을 짓기 위해서 걸리는 시간은, 해당 건물을 짓기 위해 우선적으로 지어야 하는 건물들 중에서 가장

오래 걸리는 시간 + 특정 건물을 짓기 위해서 걸리는 시간" 이 된다.

코드로 표현하면 다음과 같다.

while (Q.empty() == 0)
{
    int Cur = Q.front();
    Q.pop();
 
    for (int i = 0; i < V[Cur].size(); i++)
    {
        int Next = V[Cur][i];
        Entry[Next]--;
 
        Result[Next] = Bigger(Result[Next], Result[Cur] + Build_Time[Next]);
        if (Entry[Next] == 0) Q.push(Next); 
    }
}

line 11)과 같이 걸린 시간 중에서 가장 오래 걸리는 시간으로 계속해서 갱신해주는 과정이 필요하다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 510
using namespace std;
 
int N;
int Entry[MAX], Build_Time[MAX];
int Result[MAX];
vector<int> V[MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Build_Time[i];
        while (1)
        {
            int a; cin >> a;
            if (a == -1) break;
            V[a].push_back(i);
            Entry[i]++;
        }
    }
}
 
void Solution()
{
    queue<int> Q;
    for (int i = 1; i <= N; i++)
    {
        if (Entry[i] == 0)
        {
            Q.push(i);
            Result[i] = Build_Time[i];
        }
    }
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front();
        Q.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i];
            Entry[Next]--;
 
            Result[Next] = Bigger(Result[Next], Result[Cur] + Build_Time[Next]);
            if (Entry[Next] == 0) Q.push(Next); 
        }
    }
 
    for (int i = 1; i <= N; i++) cout << Result[i] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}