[C++] 2056 - 작업 (골드5)

1. 문제 설명

 

2056번: 작업

 

---

2. 아이디어

 

이전에 음악 프로그램인가? 몇 번 접해본 유형의 문제라 위상 정렬 알고리즘을 쓰면 되겠다는 걸 금방 캐치했다.

당시에 C++을 얼마 써보지 않아서 동적할당 연습 겸 배열을 사용했는데,

나중에 SCPC에서 알게 된 거지만 배열은 크기가 100,000까지로 제한되어 있어서

벡터에 충분한 크기의 공간을 상수로 넣어주는 게 훨씬 편하다.

 

위상 정렬인 것만 알면 그 후로 로직 자체는 간단하다.

선행 조건이 없는 작업부터 큐에 담고 하나씩 빼면서 이후 작업의 진입 차수를 1씩 제거하면

쉽게 답을 얻어낼 수 있다.

 

---

3. 코드

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

using namespace std;

int main(void) { // 전형적인 위상 정렬 문제
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n; cin >> n;

    vector<int> graph[10001];
    int* indegree = new int[n+1];
    int* cost = new int[n+1];
    int result[10001];
    int t, m;

    for (int i=0; i < n+1; i++) {
        indegree[i] = 0;
        cost[i] = 0;
        result[i] = 0;
    }

    for (int i = 1; i < n+1; i++) {
        cin >> t >> m;

        cost[i] = t;
        for (int j = 0; j < m; j++) {
            int node;
            cin >> node;
            graph[node].push_back(i);
            indegree[i]++;
        }
    }

    priority_queue<int> queue;

    for (int i = 1; i < n+1; i++) {
        if (indegree[i] == 0) {
            queue.push(i);
            result[i] = cost[i];
        }
    }

    int tmp;
    while (!queue.empty()) {
        tmp = queue.top();
        queue.pop();
        for (auto i : graph[tmp]) {
            indegree[i]--;
            if (indegree[i] == 0) {
                queue.push(i);
            }
            if (result[i] < result[tmp] + cost[i]) {
                result[i] = result[tmp] + cost[i];
            }
        }
    }

    sort(result, result + n + 1);
    cout << result[n];

    return 0;
}