[위상 정렬] BOJ 2056 작업

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

2056번: 작업

 

문제 해결 알고리즘

 

전형적인 위상 정렬 알고리즘을 활용한 문제이다.

 

작업 시간이 있는 것이 좀 다른데, 이것은 계속해서 결괏값을

먼저 해야할 작업이 걸린 시간 + 현재 해야할 작업이 걸리는 시간과 계속 비교해주면서 더 큰 쪽을 결괏값에 대입해준다.

아래의 링크에 위상 정렬 알고리즘에 대한 자세한 설명이 나와있다.

https://kimmessi.tistory.com/207

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int N;
int indegree[10002];
int Time[10002];
vector<int> graph[10002];
int ans = 0;


void topologySort(){

    vector<int> result(10001);
    queue<int> q;

    for(int i=1;i<=N;i++){ 
        if(indegree[i] == 0){
            q.push(i);
            result[i] = Time[i];
            ans = max(ans, Time[i]);
        }
    }

    while(!q.empty()){
        
        int now = q.front();
        q.pop();

        for(int i=0;i<graph[now].size();i++){
            
            indegree[graph[now][i]]--;

            result[graph[now][i]] = max(result[graph[now][i]], result[now] + Time[graph[now][i]]);

            if(indegree[graph[now][i]] == 0){
                q.push(graph[now][i]);

                ans = max(ans, result[graph[now][i]]);
            }
        }
    }
    
    cout << ans;

}

int main(){
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    cin >> N;

    for(int i=1;i<=N;i++){
        int a, b; cin >> a >> b;

        Time[i] = a;

        for(int j=0;j<b;j++){
            int c; cin >> c;
            graph[c].push_back(i);
            indegree[i]++;
        }
    }

    topologySort();
}