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

백준

---

🤔문제 이해

선행관계가 있는 작업은 선행 작업을 모두 마쳤을 때 수행될 수 있으므로 순서대로 작업하다가 특정 건물의 건설이 완료할 때까지 걸리는 최소 시간을 구하면 된다.

---

💡첫번째 아이디어

동시에 작업될 수 있는 작업들 중 시간이 적게 걸리는 작업이 먼저 다 수행되어야 하므로 priority queue를 사용하면 된다.

 

🔥풀이🔥

 

pq에서 가장 시간이 적게 걸리는 작업을 먼저 수행하고 그 작업 다음에 수행될 수 있는 작업의 in_degree를 하나 줄여준다.

in_degree를 줄였을 때 그 값이 0이라면 다음에 바로 수행할 수 있으므로 pq에 현재와 다음 작업의 수행시간을 더한 값과 다음 정점을 넣어준다. 

위 과정을 반복하다가 찾고자 하는 작업이 pop될 때 그 작업의 수행시간을 출력해주면 된다.

---

아래는 제출한 코드이다.

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

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    int t;
    cin >> t;
    int n, k, x, y, w;

    while (t--) {
        cin >> n >> k;

        int time[1002] = {0,};
        int in_degree[1002] = {0,};
        for (int i = 1; i <= n; i++) {
            cin >> time[i];
        }

        vector<vector<int>> v;
        v.resize(n+1);
        for (int i = 0; i < k; i++) {
            cin >> x >> y;
            v[x].push_back(y);
            in_degree[y]++;
        }
        cin >> w;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int i = 1; i <= n; i++) {
            if (!in_degree[i]) {
                pq.push({time[i], i});
            }
        }

        while (!pq.empty()) {
            int end_time = pq.top().first;
            int num = pq.top().second;
            pq.pop();
            if (num == w) {
                cout << end_time << "\n";
                break;
            }
            for (int next: v[num]) {
                in_degree[next]--;
                if (!in_degree[next]) {
                    pq.push({end_time + time[next], next});
                }
            }
        }
    }
}