[C++][백준 1005] ACM Craft

[문제]

1005번: ACM Craft (acmicpc.net)

1005번: ACM Craft

[문제 풀이]

위상 정렬을 이용해서 쉽게 접근이 가능한 문제이다.

위상 정렬에서는 아래와 같은 그림이 있다면 1번부터 접근을 해서 2번과 3번의 수치를 1씩 낮춘다.

그렇게 해서 2와 3이 자신한테 오는 간선이 0이 된다면 이를 큐에 집어 넣고 큐의 사이즈가 0이 될때까지 이를 반복한다.

해당 문제에서 요구하는 w가 작업을 하는데 걸리는 시간이란건 반대로 말하면 w를 시작하기까지 가장 오래 걸리는 시간을 뜻하고 이는 1 -> 3 -> 4 순으로 가면 해결이 된다.

고로, 기존의 위상 정렬 알고리즘에서 cost배열을 만들어 둔 뒤 cost2[next] = max(cost2[next], cost2[cur] + cost[next]) 라는 식을 이용해서 쉽게 해결이 가능하다.

[회고]

위상정렬 알고리즘을 배우고 나서 풀어보니까 확실히 쉽게 풀린다. 난이도는 골드3이지만 사실 상 위상정렬 알고리즘을 알고 있는지, 이를 기초적으로 응용할 수 있는지를 묻는 문제였다.

[코드]

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

using namespace std;

vector<int> adj[1005];
vector<int> result;
int cost[1005];
int cost2[1005];
int deg[1005];
int n,k,w;

void solve(){

    queue<int> q;
    
    for(int i = 1;i<=n;i++){
        if(deg[i] == 0){
            q.push(i);
            result.push_back(i);
            cost2[i] = cost[i];
        }
    }

    while(q.size() > 0){
        int cur = q.front();
        q.pop();

        for(int i = 0;i<adj[cur].size();i++){
            int next = adj[cur][i];
            deg[next]--;
            if(deg[next] == 0){
                q.push(next);
                result.push_back(next);
            }
            cost2[next] = max(cost2[next],cost2[cur] + cost[next]);
        }
    }
    cout<<cost2[w]<<endl;
    return;
}

void reset(){
    for(int i = 0;i<1002;i++){
        cost[i] = 0;
        cost2[i] = 0;
        deg[i] = 0;
    }

    result.clear();

    for(int i = 0;i<1002;i++){
        adj[i].clear();
    }
}

int main(){
    int testcase;
    cin>>testcase;
    while(testcase--){
        cin>>n>>k;

        for(int i = 1;i<=n;i++){
            cin>>cost[i];
        }
        for(int i = 0;i<k;i++){
            int a,b;
            cin>>a>>b;
            adj[a].push_back(b);
            deg[b]++;
        }

        cin>>w;
        solve();
        reset();
    }
    return 0;
}