[JS] 백준 1520번 : 내리막 길 - 구현, 그래프이론, DFS, 다이나믹프로그래밍(DP)

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

1520번: 내리막 길

 

 

📋풀이방법

1. 상하좌우 DFS로 뻗어나간다.

2. 이때 -1로 초기화한 2차원 배열 dp에 목적지까지 도착했는지에 대한 값을 기록한다.

3. 기록하면서 만약 -1이 아니고(방문을 했고)  그 좌표에 값이 있다면 그 값을 return함으로 써 뻗어나가지 않고, 미리 도착을 예상할 수 있다.

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let [M, N] = input[0].split(" ").map(Number);
let arr = [];
for (let i = 0; i < M; i++) {
  arr[i] = input[i + 1].split(" ").map(Number);
}

let dx = [1, 0, 0, -1];
let dy = [0, 1, -1, 0];
let dp = Array.from({ length: M }, () => Array(N).fill(-1));

let DFS = (y, x) => {
  if (dp[y][x] != -1) {
    return dp[y][x];
  }
  if (y == M - 1 && x == N - 1) {
    return 1;
  } else {
    let cnt = 0;
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
        if (arr[y][x] > arr[ny][nx]) {
          cnt += DFS(ny, nx);
        }
      }
    }
    dp[y][x] = cnt;
    return cnt;
  }
};

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

 

 

💢어려웠던 점

1. 메모제이션을 생각해내지 못했다.

-DFS만 이용하면 시간초과가 나는데 메모제이션을 생각하지 못했다.

-기존에 사용했던 visited 2차원배열에 dp처럼 기록을 해서 시간을 줄이는 방법이다.

-만약 뻗어나갔던 DFS가 도착했다면 1을 반환해서 지나왔던 경로에 누적하고, 좌표에 기록한다.

즉 지나왔던 경로에 누적된 값이 나중에 그 경로를 다시 지나가게 되는 경우가 생기면 뻗어나가지 않고, 기록되있던 값을 반환함으로써 시간이 절약되는 것이다.