백준 1005번: ACM Craft (C++)

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

1005번: ACM Craft

언뜻 보기에는 최단 경로를 구하는 문제인 듯해 보이지만 간선이 아닌 노드에 건물의 시간 값이 들어있기 때문에 최단 경로 문제가 아니다.

어떤 한 노드로 가는 길에 건물들을 다 짓는 데 걸리는 시간을 구하는 문제다.

건물을 짓는 데에는 순서가 있고, 이 순서를 코드로 짜야하는데 이 시점에서 Topological Sort를 떠올릴 수 있다.

 

문제에 나와있는 예시처럼 1번에서 4번 건물까지 지으려 할 때,

1번 건물에서 10초

2번 건물에서 1초, 3번 건물에서 100초

4번 건물에서 10초

가 소요된다.

 

1, 2, 3, 4 모든 건물을 지어야 하기 때문에 1번 건물 (10초) + 3번 건물 (100초) + 4번 건물 (10초)

>> 총 120초가 걸린다.

여기서 2번 건물이 포함되지 않은 이유는 3번 건물을 100초 동안 지을 때, 이미 2번 건물은 1초 만에 완성되었기 때문이다.

 

즉, 각 노드로 가면서 해당 노드까지 건물을 지은 시간을 갱신해주되 갱신될 수 있는 최댓값을 갱신하면 된다.

노드에서 노드로 가는 방식은 Topological Sort를 이용하면서 구현한다.

 

[AC 코드]

#include <iostream>
#include <vector>
#include <queue>
#define MAX 1001
#define INF 987654321
using namespace std;

int T;
int n, k;
int delay[MAX];
int inDegree[MAX];
vector<int> adj[MAX];
vector<int> result;

void init() {
    for (int i = 1; i <= n; i++) {
        delay[i] = 0;
        inDegree[i] = 0;
        while (!adj[i].empty()) {
            adj[i].pop_back();
        }
    }

    return;
}

void topologicalSort(int node) {
    vector<int> dist(n + 1, 0);
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
            dist[i] = delay[i];
        }
    }

    while (!q.empty()) {
        int now = q.front();

        q.pop();
        for (int i = 0; i < adj[now].size(); i++) {
            int next = adj[now][i];

            dist[next] = max(dist[next], dist[now] + delay[next]);
            //cout << dist[next] << '\n';
            inDegree[next] -= 1;
            if (inDegree[next] == 0) {
                q.push(next);
                //cout << next << ' ';
            }
        }
    }

    result.push_back(dist[node]);
}

int main()
{
    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            cin >> delay[i];
        }

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

        int w;
        cin >> w;
        topologicalSort(w);

        init();
    }

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << '\n';
    }

    return 0;
}