백준 JS 1005번 ACM Craft. DP

첫 번째 풀이

1. DFS + DP 풀이로 접근하면 해결되지 않을까 생각하고 풀었다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim()
  .split("\\n");
const T = +input.shift();

class Next{
  constructor(){
    this.obj = {}
  }
  push(X,Y){
    if(this.obj[X] === undefined){
      this.obj[X] = {before : [], after : []}
    }
    this.obj[X].after.push(Y)
    if(this.obj[Y] === undefined){
      this.obj[Y] = {before : [], after : []}
    }
      this.obj[Y].before.push(X)
  }
}

for(let i=0; i<T; i++){
  const [N,K] = input.shift().split(" ").map(Number)
  const DArr = [0,...input.shift().split(" ").map(Number)]
  const XYArr = input.splice(0,K).map(v => v.split(" ").map(Number))
  const W = +input.shift()

  const XYObj = new Next()
  for(let [X,Y] of XYArr){
    XYObj.push(X,Y)
  }

  const DP = Array.from({length:1001},()=>0)
  DP[W] = DArr[W]
  const Queue = [];
  if(!XYObj.obj[W]){
    console.log(DArr[W])
    continue;
  }
  for(let item of XYObj.obj[W].before){
    Queue.push(item)
  }
  let str = 0;
  while(Queue.length !== 0){
    const current = Queue.shift();
    const After = XYObj.obj[current].after
    const Before = XYObj.obj[current].before
    let max = 0;
    for(let item of After){
      if(max < DP[item]){
        max = DP[item]
      }
    }
    if(DP[current] < max + DArr[current]){
      DP[current] = max + DArr[current]
    }
    
    if(Before.length === 0){
      str = current
    }
    for(let item of Before){
      Queue.push(item)
    }
  }
  console.log(DP[str])
}

위 풀이 방법은 DP가 적용되지 않은 듯 했다. 시간초과가 나왔고 DP를 사용하려면 Queue를 사용할 순 없을 듯 하다.

---

두 번째 풀이

1. 적극적으로 DP를 사용하기 위해 Queue를 삭제했다.
2. 이 문제에서는 순서가 배열의 순서대로 진행되지 않기 때문에 재귀를 사용하여 DP사용.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim()
  .split("\\n");
const T = +input.shift();
//Next의 obj에 건물을 짓기위한 before 건물과, 건물을 지을 수 있는 after배열을 각각 선언.
class Next{
  constructor(){
    this.obj = {}
  }
  push(X,Y){
    if(this.obj[X] === undefined){
      this.obj[X] = {before : [], after : []}
    }
    this.obj[X].after.push(Y)
    if(this.obj[Y] === undefined){
      this.obj[Y] = {before : [], after : []}
    }
      this.obj[Y].before.push(X)
  }
}

for(let i=0; i<T; i++){
  const [N,K] = input.shift().split(" ").map(Number)
  const DArr = [0,...input.shift().split(" ").map(Number)]
  const XYArr = input.splice(0,K).map(v => v.split(" ").map(Number))
  const W = +input.shift()

	//각각의 건물에 필요한 건물과 지을 수 있는 건물을 before after 배열에 push한다.
  const XYObj = new Next()
  for(let [X,Y] of XYArr){
    XYObj.push(X,Y)
  }
	//DP는 i번째 건물을 짓기위한 시간을 넣는 배열이다.
  const DP = Array(N+1).fill(-1)

  function findDP(A) {
    if(DP[A] !== -1){
      return DP[A]
    }
    //obj[A]가 존재하지 않는다는 것은 단독으로 지을 수 있는 건물이라는 뜻
    if(!XYObj.obj[A]){
      DP[A] = DArr[A]
      return DArr[A]
    }
    const before = XYObj.obj[A].before
	//before의 길이가 0이라는 것은 건물을 짓기위해 필요한 건물은 없지만 지을 수 있는 건물만 존재한다는 뜻
    if(before.length === 0){
      DP[A] = DArr[A]
      return DArr[A]
    }
	//arr 배열에는 해당 건물을 짓기 위해 필요한 건물들을 짓기 위한 시간을 push한다.
    const arr = []
    for(let i=0; i<before.length; i++){
      const B = before[i]
      arr.push(findDP(B))
    }
	//arr 배열에서 구한 값의 가장 큰 값을 해당 건물을 짓는 시간에 더한다.
    DP[A] = Math.max(...arr) + DArr[A]
    return DP[A]
  }
  console.log(findDP(W))
}