🎲 백준 1520번 내리막길

백주 1520번

🧸 답을 보고도 이해하는데 꽤나 걸렸다.. DFS+DP문제라니 이제 이런 문제에도 익숙해져야한다..!
🎨 참고코드

코드

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

const [Y, X] = input.shift().split(" ").map(Number);
input = input.map((item) => item.split(" ").map(Number));

//-1로 초기화 : 방문 안했다는 의미
const dp = Array.from(new Array(Y), () => new Array(X).fill(-1));

const dir = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
];

const DFS = (i, j) => {
  //탐색지점이 도착점일 경우
  if (i === Y - 1 && j === X - 1) {
    return 1;
  }

  //탐색지점이 이전에 방문한 곳일 경우 이미 dp에 값이 있음
  if (dp[i][j] !== -1) {
    return dp[i][j];
  }

  let count = 0;

  for (let d = 0; d < 4; d++) {
    const nextY = i + dir[d][0];
    const nextX = j + dir[d][1];

    //현재 지점의 상하좌우 지점이 배열의 범위에 속해있고 내리막길이라면
    if (
      nextX >= 0 &&
      nextX < X &&
      nextY >= 0 &&
      nextY < Y &&
      input[nextY][nextX] < input[i][j]
    ) {
      count += DFS(nextY, nextX);
    }
  }

  dp[i][j] = count;
  return count;
};

console.log(DFS(0, 0));