[백준][위상정렬] 1005 ACM CRAFT NodeJs 구현

     

목차

 

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

문제

 

 

 

문제 구현 방향

result[next] = max(result[next], result[cur] + time[next]); 

정점 next의 최소 건설 시간은 선행 정점이 모두 지어진 시간에 자신의 건물을 짓는 시간을 더한 값이다.

위상정렬에서 여기까지 생각해야 되서 어려웠다.

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

class Queue {
  constructor() {
    this.queue = new Map();
    this.front = 0;
    this.end = 0;
  }
  push(num) {
    this.queue.set(this.end, num);
    this.end++;
  }
  size() {
    return this.queue.size;
  }
  pop() {
    if (this.size() === 0) return undefined;
    const item = this.queue.get(this.front);
    this.queue.delete(this.front);
    this.front++;
    if (this.size() === 0) {
      this.front = 0;
      this.end = 0;
    }
    return item;
  }
}

let idx = 1;
while (idx < input.length) {
  q = new Queue();
  let [N, K] = input[idx].trim().split(" ").map(Number);
  let degree = Array(N + 1).fill(0);
  idx++;
  let time = input[idx].trim().split(" ").map(Number);
  let adj = Array.from({ length: N + 1 }, () => []);
  idx++;
  for (let i = 0; i < K; i++) {
    let [from, to] = input[idx + i].trim().split(" ").map(Number);
    adj[from].push(to);
    degree[to]++;
  }
  idx += K;
  let target = +input[idx];
  idx++;

  let result = Array(N + 1).fill(0);
  for (let i = 1; i <= N; i++) {
    if (degree[i] === 0) {
      q.push(i);
      result[i] = time[i - 1];
    }
  }

  m = 0;
  let cnt = 1;
  for (let i = 1; i <= N; i++) {
    if (q.size() === 0) {
      return;
    }
    let t = q.pop();
    for (let k of adj[t]) {
      degree[k]--;
      result[k] = Math.max(result[k], result[t] + time[k - 1]);
      if (degree[k] === 0) {
        q.push(k);
      }
    }
    cnt++;
  }
  console.log(result[target]);
}