백준 2056 작업 | C++

 

 

 

이번 포스팅은 백준 2056번 작업입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/2056

2056번: 작업

 

 

 

기본 알고리즘

위상 정렬 Topological Sort

 

풀이

최소 시간을 갱신하는 조건 

line42

result[next] = max(result[next], result[cur] + time[next]); 

 

정점 next의 최소 건설 시간은 선행 정점이 모두 지어진 시간에 자신의 건물을 짓는 시간을 더한 값이다.

 

 

 

전체 코드

 

//백준2056 작업                                                                
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main() {
    int N;
    cin >> N;
 
    vector<int> adj[10002];
    int inDeg[10002] = { 0, };
    queue<int> q;
    int time[10002];
    int result[10002];
    for (int i = 1; i <= N; i++) {
        cin >> time[i];
        int preNum;
        cin >> preNum;
        for (int j = 0; j < preNum; j++) {
            int preBuild;
            cin >> preBuild;
            adj[preBuild].push_back(i);
            inDeg[i]++;
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (inDeg[i] == 0) {
            q.push(i);
        }
        result[i] = time[i];
    }
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 0; i < adj[cur].size(); i++) {
            int next = adj[cur][i];
            inDeg[next]--;
            result[next] = max(result[next], result[cur] + time[next]);
 
            if (inDeg[next] == 0) {
                q.push(next);
            }
        }
    }
 
    int ans = -1;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, result[i]);
    }
    cout << ans;
 
    return 0;
}