(C++) BOJ 백준 1005번 ACM Craft / 위상 정렬(Topology Sort)

BOJ.1005 ACM CRAFT 문제

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

문제 설명

---

• 문제에서 입력으로 주어지는 건물이 지어지기까지의 최단 시간을 구하는 문제
• 특정 건물을 짓기전에 먼저 지어야하는 건물의 순서가 주어진다
• 먼저 지어야 하는 건물들을 지으면서 입력으로 주어지는 W에 해당하는 건물이 지어지기 까지의 시간을 구하면 된다

문제 풀이

---

• 이 문제와 같이 순서가 주어지고 먼저 해결해야할 작업이 있을때의 경로에 관한 문제는 위상 정렬(Topology Sort)로 해결할 수 있다.
• 위상정렬(Topology Sort)는 가장 먼저 시작할 수 있는 일이 담긴 노드를 큐(Queue)에 넣어주고 시작한다.
• 가장 앞에 있는 노드를 꺼내고 해당 노드와 연결된 간선을 모두 제거한다.
• 간선들을 제거하면서 먼저 수행되어야할 작업이 담긴 노드가 0개인 노드들에 대해서 다시 큐에 넣어준다. 이 4가지 작업을 반복한다.
• ACM CRAFT 문제에서는 위상정렬을 수행하면서 특정 노드 A가 있다고 가정해보면, A까지 오기전 작업들중 가장 오래 걸리는 작업의 시간을 저장하며 수행한다.
• 이때, W까지 오기까지의 저장된 시간에 W건물을 짓는 시간을 더해주면 정답이 나오게 된다.

코드

---

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define FOR(i,N) for(int i=1; i<=N; i++)
int T;
int N, K, W;
int buildTime[1001];
vector<int> buildSeq[1001];
int buildCount[1001];
int completeTime[1001];
void build(queue<pair<int,int>>& q) {
    while(!q.empty()) {
        int cur = q.front().first;
        int curTime = q.front().second;
        if(cur==W) {
            cout << curTime << '\n';
            return;
        }
        q.pop();
        for(int i=0; i<buildSeq[cur].size(); i++) {
            buildCount[buildSeq[cur][i]]--;
            completeTime[buildSeq[cur][i]] = max(completeTime[buildSeq[cur][i]], curTime + buildTime[buildSeq[cur][i]]);
            if(buildCount[buildSeq[cur][i]] == 0) {
                q.push({buildSeq[cur][i], completeTime[buildSeq[cur][i]]});
                buildCount[buildSeq[cur][i]] = -1;
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while(T--) {
        cin >> N >> K;
        FOR(i,N) {
            cin >> buildTime[i];
            buildCount[i] = 0;
            completeTime[i] = 0;
            buildSeq[i].clear();
        }
        FOR(i,K) {
            int first,second;
            cin >> first >> second;
            buildSeq[first].push_back(second);
            buildCount[second]++;
        }
        cin >> W;
        queue<pair<int,int>> q;
        FOR(i,N) {
            if(buildCount[i] == 0) {
                q.push({i,buildTime[i]});
                completeTime[i] = buildTime[i];
            }
        }
        build(q);
    }
    return 0;
}