[Baekjoon] #1890 점프 (Node.js)

📝 문제

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

☃️ 풀이

DFS와 DP를 함께 활용해야 시간 초과 오류가 발생하지 않는다.

x, y 좌표 0, 0부터 시작하여 각 지점에서 목적지까지 도달할 수 있는 경로의 수를 dp 배열에 저장한다.

탐색 알고리즘의 흐름은 다음과 같다.

a. 목적지 좌표인 n, n에 도착하면 1을 반환한다. 
b. 도착한 곳이 이전에 방문한 적 없는 곳이라면 dp 배열에서 해당 좌표에 대한 값을 0으로 초기화한다. 
   그리고 현재 좌표에 지정된 점프 횟수만큼 오른쪽, 아래쪽으로 점프했을 때의 좌표를 구하여 탐색한다.
c. 전에 방문한 적 있는 좌표에 도달하면 dp 배열에서 해당 좌표에 대한 값을 출력한다.

이 때, 문제에서 경로의 개수는 $2^{63}$-1보다 작거나 같다고 명시했다. 자바스크립트의 Number 자료형은 -$2^{53}$+1부터 $2^{53}$-1까지의 수를 표현할 수 있기 때문에 BigInt 자료형을 사용해야 한다.

BigInt 자료형에 대한 내용은 해당 포스트에서 가볍게 설명해두었다.

💻 소스 코드

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

const path = input.map((arr) => arr.split(' ').map(Number));
const dp = Array.from({ length: n }, () => Array.from({ length: n }, () => -1));

function search(x, y) {
  if (x === n - 1 && y === n - 1) return 1n;

  if (dp[y][x] === -1) {
    dp[y][x] = 0n;

    const jump = path[y][x];
    const nx = x + jump;
    const ny = y + jump;

    if (nx < n) dp[y][x] += search(nx, y);
    if (ny < n) dp[y][x] += search(x, ny);
  }

  return dp[y][x];
}

search(0, 0);

console.log(`${dp[0][0]}`);