[BOJ] 1516 : 게임 개발

1516 : 게임 개발

풀이

위상정렬

vector v[i]는 정점i에서 나가는 정점들의 집합,

degree[i]는 정점i의 진입차수 (들어오는 간선수)

time은 정점i(번째 건물)를 건설하는데 걸리는 시간이다.

기본적인 위상정렬처럼 진입차수가 0인것부터 큐에넣은뒤 빼면서 v[i]집합안의 인덱스들에도 접근하여

해당 degree를 빼고, degree가 0이된다면 큐에 다시 넣는 방법으로 탐색한다.

하지만 이때 가장 오래걸리는 시간(임계값)을 탐색해야 되므로

ans[v[x][j]] = max(ans[x]+time[v[x][j]],ans[v[x][j]]);

코드로 계산한다. 그래프를 그림을 그려보면 이해하기 쉽다.

현재 내값과, 전에방문하는건물의 총시간+현재건물의 시간중의 큰값을 고른다.

즉, 마지막에 방문하는 건물의 총시간+현재건물의 시간이 더 커지면 갱신을 하는것이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
queue<int> q;
vector<int> v[501];
vector<int> ans(501);
int degree[501];
int time[501];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        time[i] = tmp;
        cin >> tmp;
        while (tmp != -1) {
            v[tmp].push_back(i);
            degree[i]++;
            cin >> tmp;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            q.push(i);
            ans[i] = time[i];
        }
    }

    for (int i = 1; i <= n; i++) {
        int x = q.front();
        q.pop();
        for (int j = 0; j < v[x].size(); j++) {
            degree[v[x][j]]--;
            ans[v[x][j]] = max(ans[x]+time[v[x][j]],ans[v[x][j]]);
            if (degree[v[x][j]] == 0) {
                q.push(v[x][j]);
            }
        }
    }

    for (int i = 1; i <= n;i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}
Written on April 7, 2019