백준 1005

이 문제는 위상 정렬(Topological Sort) 알고리즘을 사용하여 해결할 수 있습니다. 위상 정렬은 유향 그래프에서 정점들의 선후 관계에 따라서 정렬하는 알고리즘으로, 이 문제에서는 건물을 짓는 순서를 정하는 것에 활용할 수 있습니다.
우선 입력으로 주어진 건설 순서를 바탕으로 각 건물에 대해 선행 건물 목록을 저장합니다. 이를 위해 각 건물에 대한 리스트를 만들어야 합니다. 즉, N개의 건물이 있다면 1번부터 N번까지의 리스트를 만들고, 리스트의 i번째 원소는 i번 건물을 지으려면 먼저 지어야 하는 건물들의 번호를 저장합니다.

이후, 건설해야 할 건물 W를 지을 때까지 반복해서 처리합니다. W를 지으려면 먼저 지어야 하는 건물들이 모두 건설 완료된 상태여야 하므로, 위상 정렬 알고리즘을 사용해서 W까지 건설하기 위해 필요한 시간을 계산할 수 있습니다.
이를 위해서는 다음과 같은 절차를 따릅니다:

1. 진입차수가 0인 모든 건물을 큐에 추가합니다. 진입차수란, 해당 건물을 짓기 위해 먼저 지어야 하는 건물의 수를 의미합니다. 위상 정렬 알고리즘에서는 진입차수가 0인 정점부터 처리해나가므로, 진입차수가 0인 건물들을 먼저 처리하도록 합니다.

2. 큐에서 건물을 하나씩 꺼내면서, 해당 건물을 지어야 할 시간을 계산합니다. 이때, 선행 건물들 중 가장 오래 걸리는 건물을 먼저 지어야 하므로, 건물을 지을 때마다 해당 건물을 선행으로 둔 건물들의 지어지는 시간 중 가장 큰 값을 찾아서 더해줍니다.

3. 만약 건설해야 할 건물 W가 처리되었다면, 해당 건물을 지을 때까지 걸린 시간을 출력하고 종료합니다. 그렇지 않다면, 큐에서 더 이상 처리할 건물이 없을 때까지 반복합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 1001;

int N, K, W;
int buildingTime[MAX];
int inDegree[MAX];
vector<int> graph[MAX];
int result[MAX];

int topologySort()
{
    queue<int> q;

    // 진입 차수가 0인 노드를 큐에 삽입
    for (int i = 1; i <= N; i++)
    {
        if (inDegree[i] == 0)
        {
            q.push(i);
            result[i] = buildingTime[i];
        }
    }

    // 큐가 빌 때까지 반복
    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        // 현재 노드와 연결된 모든 노드들에 대하여 진입 차수 감소
        for (int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i];

            result[next] = max(result[next], result[now] + buildingTime[next]);
            inDegree[next]--;

            // 진입 차수가 0이 된 노드 큐에 삽입
            if (inDegree[next] == 0)
            {
                q.push(next);
            }
        }
    }

    return result[W];
}

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        cin >> N >> K;

        // 초기화
        for (int i = 1; i <= N; i++)
        {
            graph[i].clear();
            inDegree[i] = 0;
            result[i] = 0;
            cin >> buildingTime[i];
        }

        // 건설 순서 입력 받기
        for (int i = 1; i <= K; i++)
        {
            int X, Y;
            cin >> X >> Y;
            graph[X].push_back(Y);
            inDegree[Y]++;
        }

        cin >> W;

        cout << topologySort() << endl;
    }

    return 0;
}