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

문제

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

1516번: 게임 개발

풀이 방법

1005번 ACM Craft와 비슷한 문제다.

위상 정렬과 DP를 활용하는 문제이므로 잘 모르겠다면 위 링크를 통해 설명을 보는 것을 추천한다.

위 문제와 차이점은 입력 형식이 다르다는 점, 모든 건물의 건설 완성 시간을 출력해야 하는 점이다.

 

코드

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int N;
    scanf("%d", &N);
    vector<int> buildTime(N+1);
    vector<int> indegree(N+1, 0);
    vector<int> answer(N+1);
    vector<vector<int>> v(N+1);
    queue<int> q;
    for(int i=1; i<=N; i++)
    {
        int t;
        scanf("%d", &t);
        buildTime[i] = t;
        while(true)
        {
            int num;
            scanf("%d", &num);
            if(num == -1) break;
            v[num].push_back(i);
            indegree[i]++;
        }
    }
    
    for(int i=1; i<=N; i++)
    {
        if(indegree[i] == 0)
            q.push(i);
    }
    
    while(!q.empty())
    {
        int cur = q.front();
        //printf("%d ", cur);
        q.pop();
        for(int next : v[cur])
        {
            answer[next] = max(answer[next], answer[cur] + buildTime[cur]);
                
            indegree[next]--;
            if(indegree[next] == 0)
                q.push(next);
        }
    }
    
    //printf("\n");
    for(int i=1; i<=N; i++)
    {
        printf("%d\n", answer[i] + buildTime[i]);
    }
    return 0;
}

고찰

안보고 코딩했는데 맞춰서 기분 좋았던 문제.