[백준][dp][dfs] 1520 NodeJs 구현

     

목차

 

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

문제

 

 

코드 구현 방향

dfs + dp 로 풀어야 한다. 이때 초기 dp값을 -1로 해야 하는데 그 이유는 0인 경우에 방문 여부를 확인할 수 없기 때문이다.

 

 

 

 

코드 구현

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

let [N, M] = input[0].trim().split(" ").map(Number);

let dx = [0, 1, -1, 0];
let dy = [1, 0, 0, -1];

let dp = Array.from({ length: N + 1 }, () => Array(M + 1).fill(-1));

let board = [];
let idx = 1;
while (idx < input.length) {
  let t = input[idx].trim().split(" ").map(Number);
  board.push(t);
  idx++;
}

function searching(x, y) {
  if (x === M - 1 && y === N - 1) {
    return 1;
  }
  if (dp[y][x] !== -1) return dp[y][x];
  dp[y][x] = 0;
  let cur = board[y][x];
  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];
    if (nx < 0 || nx > M - 1 || ny < 0 || ny > N - 1) continue;
    if (cur <= board[ny][nx]) continue;
    dp[y][x] += searching(nx, ny);
  }
  return dp[y][x];
}

searching(0, 0);

console.log(dp[0][0]);