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

문제 및 풀이

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

이 문제는 건물이 지어지는데 걸리는 시간과 해당 건물을 짓기전에 지어져야 하는 건물들을 입력받고, 각 건물들을 지을 수 있는 최소 시간을 구하는 문제이다.

분류가 위상정렬인데...어렵다 ㅠ
나동빈님 의 위상정렬을 글을 참고했다. (https://blog.naver.com/ndb796/221236874984)

여기서 정의한 vector<int> v[N] 에는 건물을 지은 후 지을 수 있는 건물들을 입력받는다 (v[x]의 값들은 x를 지은 후 지을수 있는 건물들 ..)

그리고 간선이 0인 노드부터 시작해서 큐에 넣어 연결된 간선을 하나씩 지워나가는데, 하나의 노드에 연결된 간선이 0이 되는 순간 다음 건물들도 지을 수 있으므로 다시 큐에 넣어 간선을 지워나가는 작업을 반복한다.

요약하자면 다음과 같다.

• 간선이 0인 노드부터 시작해서 큐에 입력 (x)
• x를 지은 후 지을 수 있는 건물들인 v[x]를 순회하며 노드값을 1씩 감소
• 여기서 새로 간선이 0이 된 노드가 있다면, 해당 노드를 큐에 입력
• 큐가 빌 때 까지 위 작업을 반복해서 수행

코드

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

int N;
vector<int> v[505]; // v[i] : i를 지은 후 지을수 있는 건물들 
int E[505]; // E[i] : 노드 i로 입력되는 방향의 간선 개수
int T[505]; // T[i] : i를 짓는데 걸리는 시간
int dp[505]; // dp[i] : i를 짓는데 걸리는 필요한 최소 시간
int x;

void topologySort() {

    queue<int> q;
    for( int i=1; i<=N; i++) {
        if(E[i]==0) {
            q.push(i);
            dp[i]=T[i];
        }
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();

        for(int i=0; i<v[now].size(); i++) {
            int next = v[now][i];
            if (--E[next] == 0) q.push(next);
            dp[next] = max(dp[next], T[next] + dp[now]);
        }
    }

}


int main() {
    cin >> N;

    for(int i=1; i<=N; i++){
        cin>>T[i];
        while(1){
            cin>>x;
            if(x==-1) break;
            v[x].push_back(i); 
            E[i]++;
        }
    }

    topologySort();
    for(int i=1; i<=N; i++) cout<<dp[i]<<" ";
}