백준/ Gold 3 문제 , 백준 Node.js 자바스크립트 1520 내리막 길 [DFS, DP]

백준/ Gold 3 문제 , 백준 Node.js 자바스크립트 1520 내리막 길 [DFS, DP]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

 

문제 출처 🏠

 

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

1520번: 내리막 길

 

 

 

문제풀이 소감 🧑‍💻

DFS 로만 풀면 시간초과가 났다.

이런 저런 조건들을 줘봤지만, 시간 초과는 여전했다.

이후, DP를 추가로 활용하라는 힌트를 얻은 뒤 풀이가 가능했다.

 

DP를 같이 활용해서 풀어야 한다는 점이 바로 생각해내기 힘든 부분 같은데,

필히, 익혀둬야할 활용법같다. 

 

 

 

요구사항 📋

높이 (칸에 써진 숫자)가 낮은 위치로만 이동해서

오른쪽 아래 끝 지점까지 가는 경우의 수 카운트

 

 

해결 전략 📝

 

주어진 판의 상하좌우를 탐색하면서 dfs 를 진행한다.

 

이때, 시간 절약을 위해 유효성 검사가 같이 진행되어야한다. 

 

1. 끝지점에 도달했을 경우 문제에서 요구하는 경우의 수이므로 1을 더해주기 위해 1 리턴

 

2. 탐색 중간에 끝지점값보다 작아지는 경우를 탐색하는 경우 더 탐색할 필요가 없으므로 0 리턴

 

3. 탐색할 곳 dp 값이 -1 이 아닌경우 이미 경우의 수를 탐색한 곳이므로 해당 위치 부터는 새로 더 탐색할 필요가 없으므로 해당 dp 값을 리턴

 

 

위 검사중 3번 검사가 제일 중요한 핵심이다. 이미 탐색한 구간을 또 탐색할 필요가 없게 해준다.

 

 

 

 

주의 ❗

DP 초기 값은 -1로 해줘야한다. 안그러면 0도 해당 되는 경우의 수라고 판단하여 불필요한 탐색이 이뤄진다.

 

이 부분을 처음에 생각하기가 어려웠다.

 

 

정답 💯

 

 

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

const [input_N, input_M] = input[0].split(" ").map(Number);
input.shift();
const input_board = input.map((v) => v.split(" ").map(Number));

function solution(N, M, board) {
  const validate = (x, y) => {
    if (x === N - 1 && y === M - 1) return 1;
    if (board[x][y] <= board[N - 1][M - 1]) return 0;
    if (dp[x][y] !== -1) return dp[x][y];
    return "allow";
  };

  const dfs = (x, y) => {
    const result = validate(x, y);
    if (result !== "allow") return result;
    dp[x][y] = 0;
    for (let i = 0; i < 4; i++) {
      const [mx, my] = [x + dr_x[i], y + dr_y[i]];
      if (mx < 0 || mx >= N || my < 0 || my >= M) continue;
      if (board[x][y] > board[mx][my]) dp[x][y] += dfs(mx, my);
    }
    return dp[x][y];
  };
  const dr_x = [-1, 0, 1, 0];
  const dr_y = [0, 1, 0, -1];
  const dp = Array.from(Array(N), () => Array(M).fill(-1));
  let cnt = dfs(0, 0);

  return cnt;
}

console.log(solution(input_N, input_M, input_board));