[백준] 2056 작업 - javascript

📌 문제

https://www.acmicpc.net/problem/2056

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let n = Number(input[0]);
let indegrees = new Array(n + 1).fill(0);
let graph = new Array(n + 1);
let time = new Array(n + 1);

for (let i = 0; i < graph.length; i++) {
  graph[i] = [];
}
for (let i = 0; i < n; i++) {
  let arr = input[i + 1].split(" ").map(Number);
  for (let j = 0; j < arr[1]; j++) {
    graph[arr[j + 2]].push(i + 1);
    indegrees[i + 1]++;
  }
  time[i + 1] = arr[0];
}

let queue = [];
let finish_time = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
  if (indegrees[i] === 0) {
    queue.push(i);
    finish_time[i] = time[i];
  }
}

while (queue.length) {
  let x = queue.shift();
  for (let next of graph[x]) {
    indegrees[next]--;
    finish_time[next] = Math.max(
      finish_time[next],
      finish_time[x] + time[next]
    );
    if (indegrees[next] === 0) queue.push(next);
  }
}
console.log(Math.max(...finish_time));

✔ 알고리즘 : 위상정렬 + DP

✔ 간선이 어떠한 작업을 하기 위해 필요한 작업이라고 생각하고 그래프를 만든다. 간선을 추가할 때마다 도착점의 indegrees를 1증가

✔ 큐를 생성하여 선행관계가 없는 작업을 (indegrees가 0인 경우) push한다.

✔ finish_time[i]는 i번째 작업이 끝나는 시간이다.

✔ 선행관계가 없는 작업부터 수행해야 하므로 while문을 통해 queue를 탐색한다.

✔ 큐에서 뽑은 작업을 수행하며 큐에서 뽑은 작업이 선행작업인 다른 작업들의 indegrees를 감소시킨다.

✔ 선행작업이 한개가 아닐 수 있으므로 Math.max메서드를 사용하여 finish_time 을 결정한다.

✔ indegrees가 0이 되는 경우 작업할 수 있는 상태이므로 queue에 push한다.

✔ finish_time 배열의 최댓값이 모든 작업을 끝내는 데 걸리는 최소 시간이다.

✔ 난이도 : 백준 기준 골드 4