[백준] 게임 개발

문제 링크: https://www.acmicpc.net/problem/1516

오랜만에 위상정렬 개념을 생각해보니 떠오르지 않아서 기본적인 위상정렬 문제를 가져왔다.

• 위상정렬(Topology Sort)이란?
  순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.
  방법

1. 진입차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.
3. 간선 제거 이후에 진입차수가 0이된 정점을 큐에 삽입한다.
4. 큐가 빌 대까지 2번과 3번 과정을 반복한다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상정렬의 결과이다.

위 문제에서는 순서를 정하라고 직접적인 힌트는 없지만, 건물을 짓는 데 선후 관계가 있음을 알려서 순서가 있음을 내포한다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// parent -> child
vector <int> graph[501];
queue <int> q;
int times[501];
// priors : i번째 건물을 짓는 데 필요한 건물의 수
int priors[501] = {0};
int result[501] = {0};
int n;

int main(void){
    int t, prior;
    cin >> n;
    for(int i = 1;i <= n;i++) {
        cin >> t;
        times[i] = t;
        while(1){
            cin >> prior;
            if(prior == -1) break;
            // 건물 하나 짓는데 그 이전에 지어야하는 건물이 여러 개일 가능성 존재
            priors[i]++;
            graph[prior].push_back(i);
        }
    }
    // 진입차수가 0인 노드를 큐에 우선 삽입
    for(int i = 1;i <= n;i++){
        if(priors[i] == 0){
            result[i] = times[i];
            q.push(i);
        }
    }
    // 위상 정렬이 완전히 수행되려면 n개의 노드 pop
    // 만약 큐가 먼저 empty되면 cycle이 있는 것이다.
    for(int i = 1;i <= n;i++){
        if(!q.empty()){
            int x = q.front();
            q.pop();
            for(int j = 0;j < graph[x].size();j++){
                int y = graph[x][j];
                result[y] = max(result[y], result[x] + times[y]);
                if(--priors[y] == 0){
                    q.push(y);
                }
            }
        }
    }
    
    for(int i = 1;i <= n;i++){
        cout << result[i] << endl;
    }
    
}

위 위상정렬의 개념을 적용하여 이 문제를 접근하면 건물별로 짓는 데 필요한 time, 먼저 지어져야 하는 건물 개수 prior을 입력받는다.
그리고 역으로 건물 간의 선후 관계를 linked list의 형태로 저장한다.

그 중 기존과 달리 vector<vector<int>>의 형태로 하면 에러가 발생한다. 왜냐면 역으로 push_back할 때 아직 메모리도 생성되지 않은 vector의 push_back 메소드하는 격이 되기 때문이다.

그래서 이번엔 vector의 array 형식으로 접근하고자 한다.
e.g. vector<int> graph[501]

그래서 예제의 결과를 시각화하면 다음과 같다.

(이미지처리하기 귀찮아)

아무래도 아직 위상정렬을 터득하지 못한 거 같아서 한 문제 더 풀고 자야겠다.