[위상 정렬] BOJ 1005 ACM Craft

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

1005번: ACM Craft

 

문제 해결 알고리즘

 

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

 

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

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

 

https://kimmessi.tistory.com/194

[위상 정렬] BOJ 2056 작업

위의 링크에 문제와 거의 같은 문제라고 봐도 된다.

 

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

 

https://kimmessi.tistory.com/207

[알고리즘] 위상 정렬 (Topology Sort) - BFS

 

소스 코드

 

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

int T, N, K, W;

int indegree[1002];
int Time[1002];
vector<int> graph[1002];

void topologySort(){
    vector<int> result(1002);
    queue<int> q;

    for(int i=1;i<=N;i++){
        if(indegree[i] == 0) {
            q.push(i);
            result[i] = 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]);


            }
        }
    }

    cout << result[W] << '\n';
}

int main(){

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> T;

    for(int i=0;i<T;i++){
        cin >> N >> K;

        for(int i=1;i<=N;i++) cin >> Time[i];

        for(int i=0;i<K;i++){
            int X, Y; cin >> X >> Y;

            graph[X].push_back(Y);

            indegree[Y]++;
        }
        
        cin >> W;

        topologySort();

        for(int i=0;i<1002;i++){
            Time[i] = 0;
            while(!graph[i].empty()) graph[i].pop_back();
        }

    }
}