1516 게임 개발

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

1516번: 게임 개발

 

이 문제는 위상정렬로 풀 수 있는 문제이다. 위상 정렬은 주로 게임에서 스킬트리와 같은 즉, 선행되어야 하는 작업이 있을 때의 순서를 어떻게 처리해야 빠른지를 풀 때 사용하는 알고리즘이다. 위상정렬의 구현은 그래프 구조에서 in-direction 의 갯수를 저장하는 배열이 가장 핵심이다. 즉 어떤 노드 K 번에 들어오는 간선의 수가 3개가 있을 때, ind[K] = 3 처럼 저장한 뒤, ind[i] 값이 0인 정점부터 큐(queue)에 넣고 순차적으로 탐색해가면 된다.

 

 

위 그림으로 설명하면

 1. ind 값이 0 인 1번 3번 노드가 queue에 넣는다.
 2. 큐에 가장 앞에 있는 노드를 방문(1 번) 한 후, 이 노드에 연결된 (2 번으로의)간선을 돌면서 ind[ graph[cur][next] ] 의 값을 -1 해준다.
     ( 그림에선 2번으로의 간선이므로, ind[2]--; )
 3. 만약 2번의 과정을 통해서 ind 값이 0 이 되면(ind[ graph[cur][next] ] == 0) 해당 노드를 queue에 push 한다.
 4. 2~3번을 반복

 

 

 

소스코드

 

#include<stdio.h>
#include<queue>
#include<vector>
 
using namespace std;
int inline max(int a, int b){return a>b?a:b;}
int n, t[501], ind[501], ans[501];
vector<int> v[501];
 
int main(){
    scanf("%d", &n);
    int p;
    for(int i=1;i<=n;i++){
        scanf("%d", &t[i]);
        while(scanf("%d", &p) == 1){
            if(p == -1) break;
            v[p].push_back(i);
            ind[i]++;
        }
    }
 
    queue< pair<int, int> > q;
    for(int i=1;i<=n;i++){
        if(ind[i] == 0){
            q.push(make_pair(i, t[i]));
            ans[i] = t[i];
        }
    }
 
    while(!q.empty()){
        int cur = q.front().first; 
        int curt = q.front().second;
        q.pop();
        for(int i=0; i<v[cur].size(); i++){
            ind[ v[cur][i] ]--;
            ans[ v[cur][i] ] = max(ans[v[cur][i]], curt + t[ v[cur][i] ]);
            if(ind[ v[cur][i] ] == 0){
                q.push(make_pair(v[cur][i], ans[ v[cur][i] ] ));
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}