[백준 1005] ACM Craft

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

위상정렬을 이용한 문제이다.

도착 위치가 3 일때,{1}->{3} 으로 바로 가는 경우와 {1}->{2}->{3}으로 다른 노드를 거쳐 가는 경우가 존재할 때, 이를 어떻게 해결할지만 조심하면 바로 풀리는 문제이다.

풀이 과정

1. 현재 노드 까지의 최솟값을 구하기 위해선, 해결해야 할 노드들을 전부 동시에 해결해야 한다.
   ⇒ 위상정렬 알고리즘 사용

2. 현재 노드의 최솟값 해결해야 할 노드들 중, 가장 오래 걸린 노드 + 현재 노드를 계산 한다.(모든 노드를 동시에 해결한다면, 제일 오래 걸린 노드가 완료될 때까지 기다려야 하기 때문)
   ⇒ 기존에 있던 값을 활용하므로 다이나믹 프로그래밍

구현

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

using namespace std;

int main()
{

    int t;
    cin>>t;
    while (t--)
    {
        int n,k;
        int build[1001]; // 짓는데 소요 시간
        int result[1001];
        int in[1001] = {0,}; // 진입 차수
        vector<vector<int>> edge(1000, vector<int>());
        cin>>n>>k;
        for(int i=1; i<=n; i++){
            cin>>build[i];
            result[i] = build[i];
        }
        for(int i=1; i<=k; i++){
            int s, e;
            cin>>s>>e;
            edge[s].push_back(e);
            in[e] ++;
        }
        int w;
        cin >> w;
        
        queue <int> q;
        for(int i=1; i<=n; i++){
            if(in[i] == 0){
                q.push(i);
            }
        }

        while (!q.empty())
        {
            int s = q.front();
            q.pop();
            for(auto& e : edge[s]){
                result[e] = max(result[e], result[s] + build[e]);
                if(--in[e] == 0){
                    q.push(e);
                }
                
            }
        }
        cout<<result[w]<<"\n";
        
    }
    



    return 0;
}