[백준/C++] 2056번 작업

백준

 

---

🤔문제 이해

어떤 작업을 수행하는 데 있어 순서가 있고 동시에 수행이 가능할 때, 순서대로 모든 작업을 수행하는 데 걸리는 시간을 구하는 문제이다.

---

💡첫번째 아이디어

위상정렬 문제로 동시에 수행되는 작업이 있고 선행에 있는 작업을 모두 수행했을 때 다음 작업 수행이 가능하므로 priority queue를 사용해야겠다고 생각했다.

 

🔥풀이🔥

1. pq에 in_degree가 0인 정점을 다 넣어준다.

2. 현재 pq의 top의 시간을 time값에 더해주고 pop을 해준다.

3. pq에 남아 있는 작업들에서 top의 시간을 빼주고 그 값들을 tmp라는 임시 queue에 넣어준다.

4. tmp에 들어있는 값들을 하나씩 빼서 pq에 넣어준다.

5. top의 다음에 수행될 수 있는 작업들의 in_degree를 -1 해줬을 때 in_degree 값이 0이라면 pq에 넣어준다.

6. 2~5번 작업을 반복하다가 pq가 비었을 때 while문을 빠져나와 time값을 출력해준다.

 

❌트러블 슈팅

값이 제대로 나왔기에 어디서 잘못된건지 가늠이 안됐다. 그러다가 풀이에서의 3번 과정을 수행할 때 pq.size()로 수행해서 그 과정에서 새로 들어간 pq 원래 pq에 남아있던 값들의 시간보다 작아서 내가 원하는 값들만 뽑아내서 시간을 업데이트해 줄 수 없었다. 

---

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

using namespace std;

int n;
vector<vector<int>> v;
int in_degree[10003];
int cost[10003];
queue<pair < int, int>>
tmp;

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

    cin >> n;
    v.resize(n + 2);

    int a, b;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i] >> a;
        for (int j = 0; j < a; j++) {
            cin >> b;
            v[b].push_back(i);
            in_degree[i]++;
        }
    }

    priority_queue<pair < int, int>>
    pq;
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == 0) {
            pq.push({-cost[i], i});
        }
    }
    int time = 0;
    while (!pq.empty()) {
        int now_cost = -pq.top().first;
        int now = pq.top().second;
        int size = pq.size();
        pq.pop();
        time += now_cost;

        for (int i = 0; i < size - 1; i++) {
            int same_time_cost = -pq.top().first - now_cost;
            int same_time_vertex = pq.top().second;
            pq.pop();
            tmp.push({same_time_cost, same_time_vertex});
        }
        while (!tmp.empty()) {
            pq.push({-tmp.front().first, tmp.front().second});
            tmp.pop();
        }
        

        for (int next: v[now]) {
            in_degree[next]--;
            if (in_degree[next] == 0) {
                pq.push({-cost[next], next});
            }
        }
    }
    cout << time;

}

 

🔗참고할 문제

거의 같은 문제라고 봐도 무방..!

[백준/C++] 2098번 외판원 순회