[BOJ 2056] 작업

각각의 작업마다 걸리는 시간이 다른 것을 $N$개를 모두 완료하기 위해 필요한 최소 시간을 구하는 문제이다. 작업들 사이에는 선행 관계가 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 하는 작업들이 있다. 

 

'선행 관계' 대놓고 위상 정렬 문제이다. 

 

위상 정렬(topological sort)은 비순환 방향 그래프(DAG)에서 각 정점들이 가지는 위상에 따라 순서대로 나열하는 것을 의미한다. 선수 과목, 게임에서의 테크 등을 생각하면 편할 것이다. 

 

각각의 건물이 지어지는 시간을 구한 다음 최댓값을 출력하면 그것이 모든 건물을 짓는데 걸리는 최소 시간이다. 

int N, cost[MAXN], in_degree[MAXN], dp[MAXN];
vector<int> v[MAXN];
queue<int> q;

int main(void) {
    fastio;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> cost[i] >> in_degree[i]; dp[i] = cost[i];
        for (int j = 1; j <= in_degree[i]; j++) {
            int prev; cin >> prev;
            v[prev].push_back(i);
        }
        if (in_degree[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int next : v[cur]) {
            in_degree[next]--;
            dp[next] = max(dp[next], dp[cur] + cost[next]);
            if (in_degree[next] == 0)
                q.push(next);
        }
    }

    cout << *max_element(dp + 1, dp + N + 1);
    return 0;
}