Javascript 백준 1890 점프

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

로직

• 게임판과 같은 사이즈의 N*N배열(check)을 만들고, 그 지점에서 몇개의 경로로 목표에 도착 가능한지를 기록

• dfs을 이용하여 탐색

• 이동은 오른쪽과 아래로만 가능

• 오른쪽으로 이동한 결과 과거에 그 지점을 탐색한 적이 있으면 check에 값이 기록되어 있음

  • 해당 지점에서 목표에 도착을 못할 경우 -1 값 기록
  • 해당 지점에서 목표에 도착 가능할 경우 경우의 수기록

주의사항 및 알게된 점

• 이 문제에서 경로의 최대 개수는 2^63-1 이하

• JavaScript의 number type의 최대 값은 2^53-1

• 따라서 BigInt를 이용하여 계산해야 함

• BigInt는 number와의 연산이 불가 [BigInt(1)+1이 불가]

• N*N배열을 만들 때 const check = Array.fill을 사용했었는데, 이 경우 check[0]과 check[1] .... 이 모두 같은 객체로 채워지게 됨

  • const arr = [[0,0,0,0],[0,0,0,0]]에서 arr[0][1]= 1 과 같이 변경시 같은 객체를 포인터하고 있기에arr 가 [[1,0,0,0],[1,0,0,0]]가 됨

const fs = require('fs');
const URI = process.platform ==='linux'? 'dev/stdin':'./1890.txt';
const inputs = fs.readFileSync(URI).toString().trim().split('\n').map((x)=>x.split(' ').map(Number));
const N = inputs.shift()[0];
const arr = inputs;
const inrange = (i,N)=>{
    if (0<=i && i<N)return true;
    return false;
};

const dfs = (r,c,N)=>{
    const v = arr[r][c];
  // 무한 루프 방지  
  if (v==0){
        check[r][c] = BigInt(-1);
        return 0;
    };

    const nr = r+v, nc = c+v;
    let value = BigInt(0); // 해당 지점에서 목표까지 갈 수 있는 경우의 수
  // 밑으로 이동  
  if (inrange(nr,N)){
        if (check[nr][c]>=1) {value += BigInt(check[nr][c])} // 과거에 간 적이 있고, 목표에 도착 가능하면 해당 값 이용
        else if (check[nr][c]==0){value += BigInt(dfs(nr,c,N))}; // 간 적이 없으면 재귀를 이용하여 탐색
    };
  // 오른쪽으로 이동
    if (inrange(nc,N)){
        if (check[r][nc]>=1) {value += BigInt(check[r][nc])}
        else if (check[r][nc]==0){value += BigInt(dfs(r,nc,N))};
    };
    if (value == 0) check[r][c] = BigInt(-1); // 도착 불가
    else check[r][c] = value; // 도착 가능
    return value;
}
const check = Array.from({ length: N }, () => new Array(N).fill(BigInt(0)));
check[N-1][N-1] = BigInt(1);
const ans = dfs(0,0,N);
if (ans == -1){console.log(0)} else {console.log(ans.toString())};