[Javascript] Algospot_JUMPGAME. 외발뛰기

🦍 문제

algospot.com :: JUMPGAME

---

🐈 문제 풀이

1. 무엇을 구해야 할까?

각 테스트케이스마다 주어진 2차원 배열의 좌상단에서 출발해 우하단에 정확히 도착할 수 있는지 여부를 출력해야한다.

2. 어떻게 구해야 할까?

좌표를 입력받아 해당 좌표의 Value값을 토대로 이동한 다음 좌표에서의 계산을 반복해나가는 재귀함수를 작성한다면 어렵지 않게 해답을 도출해낼 수 있다.

3. 특별히 고려해야 할 사항은?

위에서 작성한 재귀함수를 실행하다보면, 동일한 좌표에서의 재귀 함수를 반복적으로 실행해야 할 경우가 발생할 수 있다. 하지만 이미 방문했던 좌표에서의 결과는 이전 함수 호출에서의 결과값을 활용해 확인할 수 있으므로 메모이제이션을 통해 시간을 단축할 수 있어야한다.

---

🐕‍🦺 소스 코드

1. 메모이제이션 적용 이전

 - jump 함수 내에서 새로운 좌표에 도달할 때 마다 다음 jump 함수를 항상 재귀적으로 호출해 답을 도출하였다.

const input = require('fs')
  .readFileSync(0)
  .toString()
  .trim()
  .split('\n');

function solution() {
  let idx = 0;
  const T = Number(input[idx++]);
  const answer = [];

  for (let tc = 0; tc < T; tc++){
    const n = Number(input[idx++]);
    const arr = Array(n).fill().map(() => input[idx++].trim().split(' ').map(Number));
    const dp  = Array(n).fill().map(() => Array(n).fill(0));

    answer.push(jump(0, 0, arr, dp) ? "YES" : "NO");
  }

  return answer.join('\n')
}

function jump(r, c, arr, dp){
  if (r === arr.length - 1 && c === arr.length - 1){
    return true;
  }

  const value = arr[r][c];
  let result = false;

  for (let i = 0; i < 2; i++){
    const nr = r + value * i;
    const nc = c + value * (1 - i);

    if (nr >= 0 && nr < arr.length && nc >= 0 && nc < arr.length){
      result = result || jump(nr, nc, arr, dp);
    }
  }

  return result;
}

console.log(solution());

 

2. 메모이제이션 적용

 - jump 함수 내에서 dp 배열에 접근해 캐싱된 값이 없을때만 재귀적으로 jump 함수를 호출하도록 했다.

const input = require('fs')
  .readFileSync(0)
  .toString()
  .trim()
  .split('\n');

function solution() {
  let idx = 0;
  const T = Number(input[idx++]);
  const answer = [];

  for (let tc = 0; tc < T; tc++){
    const n = Number(input[idx++]);
    const arr = Array(n).fill().map(() => input[idx++].trim().split(' ').map(Number));
    const dp  = Array(n).fill().map(() => Array(n).fill(0));

    answer.push(jump(0, 0, arr, dp) ? "YES" : "NO");
  }

  return answer.join('\n');
}

function jump(r, c, arr, dp){
  if (dp[r][c] !== 0){
    return dp[r][c];
  }

  if (r === arr.length - 1 && c === arr.length - 1){
    return true;
  }

  const value = arr[r][c];
  let result = false;

  for (let i = 0; i < 2; i++){
    const nr = r + value * i;
    const nc = c + value * (1 - i);

    if (nr >= 0 && nr < arr.length && nc >= 0 && nc < arr.length){
      result = result || jump(nr, nc, arr, dp);
    }
  }

  return dp[r][c] = result;
}

console.log(solution());

---

---

🐖 Think

 - 메모이제이션을 활용한 다이나믹 프로그래밍 문제의 기본적인 해결 방식에 대해 이해할 수 있는 문제였다.