백준 JS 1520번 내리막 길. DP + DFS

첫 번째 풀이

1. 단순하게 DFS로 풀었다. 이 문제의 경우 DFS로만 풀게되면 시간초과가 나게 되어있다.
2. 시간초과가 나지 않게하기 위해 never라는 배열을 만들어 절대 가지 못하는 길을 체크했다.
3. 그래도 여전히 시간초과가 남. 갈 수 있는 길을 방문 했을 경우 멈추는 것이 아니라 끝까지 방문하는 알고리즘이여서 그런 듯.

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

const [M,N] = input.shift().split(" ").map(Number)
const data = input.map(v => v.split(" ").map(Number))

const arr = Array.from({ length: M }, () => Array(N).fill(0));
const stack = [[0, 0]];
const never = Array.from({ length: M }, () => Array(N).fill(true));
let line = [];
while (stack.length !== 0) {
  const [y, x] = stack.pop();
  arr[y][x]++;
  if (y === M - 1 && x === N - 1) {
    line = [];
    continue;
  }
  let goCount = 0;
  if (y !== 0 && data[y - 1][x] < data[y][x]) {
    if (never[y - 1][x]) {
      stack.push([y - 1, x]);
      goCount++;
    }
  }
  if (y !== M - 1 && data[y + 1][x] < data[y][x]) {
    if (never[y + 1][x]) {
      stack.push([y + 1, x]);
      goCount++;
    }
  }
  if (x !== 0 && data[y][x - 1] < data[y][x]) {
    if (never[y][x - 1]) {
      stack.push([y, x - 1]);
      goCount++;
    }
  }
  if (x !== N - 1 && data[y][x + 1] < data[y][x]) {
    if (never[y][x + 1]) {
      stack.push([y, x + 1]);
      goCount++;
    }
  }

  if (goCount > 1) {
    line = [];
  };
  if (goCount === 1){
    line.push([y,x])
  }
  if (goCount === 0){
    never[y][x] = false
    while(line.length !== 0){
      const [y2,x2] = line.pop()
      never[y2][x2] = false
    }
  }
}
console.log(arr[M-1][N-1]);

---

두 번째 풀이

1. DFS를 스택이 아닌 재귀로 풀고, DP에 저장함에 따라서 경우의 수를 급격하게 줄일 수 있다는 것을 알았다.

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

const [M, N] = input.shift().split(" ").map(Number);
const data = input.map((v) => v.split(" ").map(Number));
const dp = Array.from({length : M}, () => Array(N).fill(-1))
const move = [[0,1],[0,-1],[1,0],[-1,0]]
dp[M-1][N-1] = 1

function next (point) {
  const [y,x] = point
  if(dp[y][x] !== -1){
    return dp[y][x]
  }
  let count = 0;
  for(let i=0; i<4; i++){
    const y2 = y+move[i][0]
    const x2 = x+move[i][1]
    if(y2 > -1 && x2 > -1 && y2 < M && x2 < N){
      if(data[y][x] > data[y2][x2]){
        count += next([y2,x2])
      }
    }
  }
  dp[y][x] = count
  return dp[y][x]
}
next([0,0])
console.log(dp[0][0])

재귀 + DP방법을 통해 경우의 수를 빠르게 찾는 법을 배웠다.