[BOJ] 2056 작업 | 위상정렬, DP
Problem | 작업
✨ 접근 방식
- 먼저 그래프를 완성시킨다. 그리고 연결된 노드가 0이 아니라면 자신에게 오는 indegree를 저장해준다.
- queue에 indegree가 0인 것들부터 넣어주면서 dp 배열에 자신이 수행하는데 걸리는 시간을 초기화 시켜준다.
- 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));
Author And Source
이 문제에 관하여([BOJ] 2056 작업 | 위상정렬, DP), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mingsomm/BOJ-2056-작업-위상정렬-DP저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)