greentea31's Note

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

풀이 과정

건물의 여러 종류와 그 건물을 짓는 데 걸리는 시간, 그리고 건물을 지으려면 먼저 지어야 할 건물이 주어질 때, 각 건물을 짓는데 필요한 최소 시간을 구하는 문제이다.

문제에서 주어진 예시를 그림으로 표현하였다. 1번 건물을 지으려면 10초가 소요된다. 2번 건물을 지으려면 1번 건물이 완성된 이후에 지어야 하니 10 + 10 = 20초가 소요되고, 4번 건물을 지으려면 1번 건물 -> 3번 건물 -> 4번 건물 순으로 지어야 하니 10 + 4 + 4 = 18초가 소요된다.

A라는 건물을 짓는데 필요한 소요 시간은

A를 짓기 위해 먼저 지어야 하는 건물의 소요 시간들의 최대 값 + A를 짓는데 필요한 시간이다.

위의 그림으로 보았을때 Directed Acyclic Graph임을 알 수 있으니 위상 정렬을 시행해준 후, 앞에서 부터 소요시간을 계산하고 뒤의 소요시간을 계산하는 데 사용하는 DP를 시행하면서 문제를 해결할 수 있다.

소스 코드

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

int cost[501];
vector<int> directed[501];
vector<int> r_directed[501];
int inDegree[501];
queue<int> Q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, time, goal, cur;
    cin >> N;
    for (int i = 1; i < N+1; i++) {
        cin >> time;
        cost[i] = time;
        goal = 0;
        while(true) {
            cin >> goal;
            if (goal == -1) break;
            directed[goal].push_back(i);
            r_directed[i].push_back(goal);
            inDegree[i]++;
        }
    }

    for (int i = 1; i < N+1; i++) {
        if (inDegree[i] == 0) Q.push(i);
    }

    while (!Q.empty()) {
        int maxValue = 0;
        cur = Q.front(); Q.pop();

        for (int i = 0; i < r_directed[cur].size(); i++) {
            int prev_cost = cost[r_directed[cur][i]];
            if (prev_cost > maxValue) {
                maxValue = prev_cost;
            }
        }

        if (!r_directed[cur].empty()) cost[cur] += maxValue;

        for (int i = 0; i < directed[cur].size(); i++) {
            goal = directed[cur][i];
            inDegree[goal]--;

            if (inDegree[goal] == 0) {
                Q.push(goal);
            }
        }
    }

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

    return 0;
}