[C++] 백준 2056 - 작업

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

1238번: 파티

<알고리즘 분류>

  - 그래프 이론(Graph Theory)

   - 위상 정렬 (Topological Sort)

   - 다이나믹 프로그래밍(Dynamic Programming)

 

<풀이> 

  1. 위상 정렬 문제다. 아래는 예제 입력 1에 관한 내용을 그림으로 표현하였다. 

  2. 위상정렬은 간선(edge), 진입차수(Indegree)에 관한 배열과 큐(queue)를 이용하여 구현한다. 

 

  3. 하지만 이 문제는 위상정렬 구현에 그치지 않는다. 위상정렬을 진행하면서 걸리는 시간을 구해야 하는데, 문제를 쉽게 해석하면

(이전 노드까지 걸렸던 시간 + 현재 노드의 작업을 처리하는데 걸리는 시간) vs. (이전 노드까지 걸렸던 시간) 중 더 큰 것을 구해야 한다. 한마디로 dp를 추가적으로 구현해줘야 한다. 

 

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <array>

using namespace std;

int N; // 작업의 개수
vector <int> edge[1000001]; //간선 
int inDegree[1000001]; // 진입차수
int T[10001];
int TotalTime[10001];

void TopoLogicalSort(){
    priority_queue<int,vector<int>,greater<int>> pq; 
    for (int i=1; i<=N; i++){
        if (inDegree[i] == 0){
            pq.push(i);
        }
        TotalTime[i] = T[i];
    }
  
    while (!pq.empty()){
        int cur = pq.top();
        pq.pop();

        for (int j=0; j<edge[cur].size(); j++){
            int next = edge[cur][j];
            TotalTime[next] = max(TotalTime[next], TotalTime[cur]+T[next]);
            if(--inDegree[next] == 0) {
                pq.push(next);
            }
        }
    }

}


int main(){

    cin >> N;
    for (int i=1; i<=N; i++){
        int lineNum; //i번 작업에서 걸리는 시간 T[i]와 연결된 linNum개의 작업들
        cin >> T[i] >> lineNum;
        for (int j=0; j<lineNum; j++){
            int B; // 이전노드
            cin >> B;
            edge[B].push_back(i);
            inDegree[i]++;
        }
        
    }

    TopoLogicalSort();
    
    int ans = -1;
    for(int i=1; i<=N; i++){
        ans = max(ans, TotalTime[i]);
    }

    cout << ans;

}