[백준] 1516 게임 개발

문제 :

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

1516번: 게임 개발

 

풀이 :

먼저 개발할 것이 있다는 점에서 위상 정렬 문제다. 👉🏻 위상정렬 알고리즘

자신의 노드로 향하는 다른 노드가 있을때 그 노드를 v[자신].push_back(향하는 노드)로 넣어줬다.

그리고 향하는 들어오는 노드의 값을 증가시켜줬다. (개념과 반대다) 즉 indegeree[향하는노드]++

 

따라서 값을 도식화 하면 아래와 같다.

 그리고 indegree가 0인 값부터 vector 배열부터 하나씩 돌아 index에 해당하는 vector 값에 index의 건축 시간을 더해준다.

현재 q에는 indegree가 0인 1만 있다. 

1은 2, 3, 4 하위 노드를 각각 돌면서

2번 노드 = 2번 자신 + 1번 노드 값

3번 노드 = 3번 자신 + 1번 노드 값

4번 노드 = 4번 자신 + 1번 노드 값

값을 받아 sum 배열에 업데이트 해준다.

 

원래 위상 정렬의 경우 사이클이 존재해선 안된다 .. ! 근데 이 문제는 사이클이 존재한다. 즉 4번 노드를 짓기 위해서 1번을 먼저 지을 수 도 있는거고, 아니면 1-3을 거쳐 4번을 지을 방법도 있는거(Or)가 아니라 둘다 먼저 지어져야 한다(And) 따라서 가장 오래 걸리는 시간 + 자기 시간으로 계산해준다.

 

c++ 코드

//
//  1516_gameDev.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/03/03.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int N;
vector<int> v[501];
int indegree[501];
int buildTime[501];
int sum[501];
queue<int> q;

int main(){
    
    for(int i = 1; i <= N; i++){
        indegree[i] = 0; // 초기화
        sum[i] = 0;
    }
    
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> buildTime[i];
        int b;
        while(1){
            cin >> b;
            if(b == -1) break;
            v[b].push_back(i);
            indegree[i]++; // 위상 증가
        }
        
    }
    
    for(int i = 1; i <= N; i++){
        if(indegree[i] == 0){
            q.push(i);
            sum[i] = buildTime[i];
        }
    }
    
    while(!q.empty()){
        int top = q.front();
        q.pop();
        for(int i = 0; i < v[top].size(); i++){
            int next = v[top][i];
            if(--indegree[next] == 0) { q.push(next); }
            sum[next] = max(sum[next], buildTime[next] + sum[top]);

        }
        
    }
    
    for(int i = 1; i <= N; i++){
        cout << sum[i] << '\n';
    }
    
    
    
    
    return 0;
}