🎲 백준 1005번 ACM Craft

백준 1005번

💡 재귀함수를 사용해 최종적으로 구하려는 건물부터 시작했다.
💡 node 배열의 index는 건물 번호이고 값은 이 건물을 건설하기 위해 완성되어야하는 건물 번호를 저장한다.

코드

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

for (let c = 0; c < input.length; c++) {
  const [N, K] = input[c].split(" ").map(Number);
  const sec = input[c + 1].split(" ").map(Number);
  sec.unshift(0);
  const node = Array.from(new Array(N + 1), () => []);
  for (let k = 0; k < K; k++) {
    const [X, Y] = input[c + 2 + k].split(" ").map(Number);
    node[Y].push(X);
  }
  const dp = new Array(N + 1).fill(-1);

  const dpValue = (index) => {
    if (dp[index] !== -1) return dp[index];
    if (node[index].length === 0) {
      dp[index] = sec[index];
      return sec[index];
    } else {
      let max = -1;

      for (let i = 0; i < node[index].length; i++) {
        if (max < dpValue(node[index][i])) max = dpValue(node[index][i]);
      }
      dp[index] = max + sec[index];
      return max + sec[index];
    }
  };

  console.log(dpValue(input[c + 2 + K]));

  c = c + 2 + K;
}