[BOJ] 2056 작업 | 위상정렬, DP

Problem | 작업

✨ 접근 방식

1. 먼저 그래프를 완성시킨다. 그리고 연결된 노드가 0이 아니라면 자신에게 오는 indegree를 저장해준다.
2. queue에 indegree가 0인 것들부터 넣어주면서 dp 배열에 자신이 수행하는데 걸리는 시간을 초기화 시켜준다.
3. queue에서 값을 shift 시켜주면서 자신과 연결된 노드의 indegree를 줄여준다.

   이때, dp에서는 자신에게 들어오는 time의 max 값을 넣어줘야 한다.
   3을 수행하기 위해서 [3번 노드에 연결된 노드가 1,2라고 가정, 1번 노드(걸리는 시간: 6초), 2번 노드 (걸리는 시간 : 3초)] 가장 늦은 시간인 6초까지 기다려야 하기 때문이다.

• ✔️ 전체코드

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

let n = Number(input[0]);
let graph = Array.from(Array(n + 1), () => Array());
let indegree = new Array(n + 1).fill(0);
let time = new Array(n + 1);

// 그래프 완성시키기
for (let i = 1; i <= n; i++) {
  let tmp = input[i].split(" ").map(Number);
  time[i] = tmp[0];
  if (tmp[1] !== 0) {
    // 추가할 것이 있는 경우
    for (let j = 2; j < tmp.length; j++) {
      graph[tmp[j]].push(i);
      indegree[i]++;
    }
  }
}

// indegree 0인 걸 초기화시켜주고, dp 초기값 초기화
let queue = [];
let dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
  if (indegree[i] === 0) {
    queue.push(i);
    dp[i] = time[i];
  }
}
/*
console.log(dp);
console.log(queue);
*/
while (queue.length) {
  let x = queue.shift();
  for (let next of graph[x]) {
    indegree[next]--;
    dp[next] = Math.max(dp[next], dp[x] + time[next]);
    if (indegree[next] === 0) queue.push(next);
  }
}
console.log(Math.max(...dp));