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

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

1. 문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

2. 입력

첫째 줄에 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, ..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

3. 출력

첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

4. 풀이

• 위상 정렬 문제
• 각 작업이 걸리는 시간을 저장하는 배열에 저장한다.
• 각 작업의 선행 작업의 개수는 작업의 차수로 indegree 배열에 저장한다.
• 각 작업의 선행 작업 관계를 graph 백터 배열에 저장한다.
• 위상 정렬을 한다.
• 차수가 0인 작업들을 큐에 삽입한다.
• 차수가 0인 작업에 걸리는 시간은 처음에 입력 받은 시간 그대로 d 배열에 저장한다.
• 큐에서 작업들을 꺼내 연결된 작업들의 차수를 하나씩 줄여준다.
• 큐에 연결된 작업의 시간d[child]은 d[now] + arr[now], d[child] 중 최댓값이다.
• 모든 연결된 노드를 확인하고 나면 d 배열에 저장된 최댓값이 모든 작업을 완료하기 위한 최소 시간이다.

5. 처음 코드와 달라진 점

• 서로 선행 관계가 없는 작업들을 동시에 수행가능하다는 것을 제대로 구현하지 못했다.
• 서로 선행관계가 없는 작업을 두 개 실행하고 더 실행 시간이 긴 작업이 끝날 때까지 기다리고 다음 작업들을 실행하는 식으로 구현하여 제대로 구현이 안 됐다.
• 참고 블로그를 참고하여 코드를 수정했다.

6. 코드

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

using namespace std;

int indegree[10001] = {0, };
int arr[10001];
int d[10001];
vector<int> graph[10001];
int n;

void topologySort() {
  queue<int> q;

  for (int i = 1; i <= n; i++) {
    if (indegree[i] == 0) {
      q.push(i);
    }
    d[i] = arr[i];
  }


  while (!q.empty()) {
    int now = q.front();
    q.pop();

    for (int i = 0; i < graph[now].size(); i++) {
      int child = graph[now][i];
      if (--indegree[child] == 0) {
        q.push(child);
      }
      d[child] = max(d[child], d[now] + arr[child]);
    }
  }
  int answer = 0;
  for (int i = 1; i <= n; i++) {
    answer = max(answer, d[i]);
  }
  
  cout << answer;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    int t, numberOfChildren;
    cin >> t >> numberOfChildren;
    arr[i] = t;
    indegree[i] = numberOfChildren;

    for (int j = 0; j < numberOfChildren; j++) {
      int parent;
      cin >> parent;

      graph[parent].push_back(i);
    }
  }

  topologySort();
}