9주차(위상정렬) - [C++]백준2056 작업

13 May 2022 in Study on Algorithm

백준2056 작업 링크

문제

예제 입력

---

코드

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

// 각 선작업 수, 작업 비용, 작업결과
int cnt[10001], cost[10001], result[10001];
// 인접행렬
vector<int> vec[10001];
int n;

void topology_sort() {
    queue<int> q;
    // 처음 지점 추가
    for (int i = 1; i <= n; i++) {
        if (cnt[i] == 0) {
            result[i] = cost[i];
            q.push(i);
        }
    }

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        // 다음 지점 탐색
        for (int i = 0; i < vec[cur].size(); i++) {
            int nxt = vec[cur][i];
            cnt[nxt]--;
            result[nxt] = max(result[nxt], result[cur] + cost[nxt]); // 여러 작업중 가장 늦게 끝나는 시간으로 설정
            if (cnt[nxt] == 0) { // 다음 지점 추가
                q.push(nxt);
            }
        }
    }
    int ans = *max_element(result, result+(n+1));
    cout << ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

설명

이 문제는 선작업에 대한 개념이 있고 모든 작업을 완료하기 위해 필요한 최소 시간을 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector와 queue를 사용하여 구현했습니다. 위상정렬를 하기 위해서는 인접행렬과 몇개의 선작업이 있는지 저장하는 배열이 필요하고 그것으로 선작업이 없는 것들을 먼저 큐에 넣어서 실행시킵니다. 그 후에는 앞에서 했던 작업이 선작업으로 지정됬던 다음 작업을 지금 할 수 있는지 아니면 또 다른 선작업이 있는지 확인하며 최종적으로 결과들중에 최대 값을 출력합니다. 앞에서 했던 문제와 다른점은 순서에 따라 넘버링을 해주기만 했었는데 이번에는 비용이라는 조건이 있어 다른 작업이 빨리 끝나더라도 한 작업이 선작업이 없거나 적더라도 너무 늦게 끝나면 그 작업이 끝난 시간으로 출력해야합니다.

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

<algorithm>
-*max_element(시작, 끝) : 배열의 크기만큼중에 최대값 위치

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용

---

결과