백준/ Silver 1 문제 , 백준 Node.js 자바스크립트 1890 점프 [DFS, DP]

백준/ Silver 1 문제 , 백준 Node.js 자바스크립트 1890 점프 [DFS, DP]

 

 

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

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

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

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

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

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

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

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


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

 

 

 

문제 출처 🏠

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

1890번: 점프

 

 

 

 

문제풀이 소감 🧑‍💻

문제 로직은 금방 작성하였는데, 자꾸 81퍼에서 틀리는 거다.

 

대체 왜...? 진짜 아무리 로직을 봐도 틀릴게 없고, TC도 다 통과했는데 뭔지 감이 안왔었다.

 

알고보니, 자료형 문제였음. 채점 과정에서 너무 큰 수가 들어와서 그 부분을 제대로 처리를 못하던 것.

 

BigInt 를 사용하니 PASS 했다.

 

백준 문제를 많이 풀어봤지만, JS로 푼 뒤로 자료형을 다룬건 거의 처음같다.

 

그래서 처음에 생각도 못했었는데, 앞으로 주의해서 잘 확인해봐야겠다.

 

 

 

요구사항 📋

- 각 위치에 써져 있는 칸 만큼 오른쪽과 아래로만 이동하면서 오른쪽 아래 끝까지 갈 수 있는 경우의 수를 구하여라.

 

- 시작은 0,0 부터 끝은 N-1,N-1 까지이다.

 

- 왼쪽과 위쪽은 이동할 수 없다.

 

- 경로의 개수는 2^63-1보다 작거나 같다

 

해결 전략 📝

 

주어진 판의 숫자만큼 오른쪽과 아래를 탐색하면서 dfs 를 진행한다.

 

오른쪽과 아래만 탐색하면 되므로 x와 y에 각각 한번씩 숫자만큼 더해서 확인한다.

 

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

 

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

 

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

 

 

 

 

주의 ❗

 

 " 경로의 개수는 2^63-1보다 작거나 같다. " 

 

경로의 개수 숫자 범위가 크므로 Number을 사용해서 풀면 80% 정도에서 계속 틀릴 것이다.

 

이것을 해결하려면, Number가 아닌 BigInt를 사용해서 할당해야한다.

 

아주 중요한 부분이다.

 

 

 

정답 💯

 

 

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

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

function solution(N, board) {
  const move = (location, dist, check) => {
    return check === 0
      ? [location[0] + dist, location[1]]
      : [location[0], location[1] + dist];
  };

  const validate = (x, y) => {
    if (x === N - 1 && y === N - 1) return 1;
    if (dp[x][y] !== BigInt(-1)) return dp[x][y];

    return "allow";
  };

  const dfs = (x, y) => {
    const check = validate(x, y);
    if (check !== "allow") return BigInt(check);
    dp[x][y] = BigInt(0);
    for (let i = 0; i < 2; i++) {
      const [mx, my] = move([x, y], board[x][y], i);
      if (mx < 0 || mx >= N || my < 0 || my >= N) continue;
      dp[x][y] += dfs(mx, my);
    }

    return dp[x][y];
  };

  const dp = Array.from(Array(N), () => Array(N).fill(BigInt(-1)));
  const answer = dfs(0, 0);

  return answer.toString();
}

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