[Javascript/자바스크립트] 백준 16173번 점프왕 쩰리 (Small)

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

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "dev/stdin" : "./input.txt";
const [n, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

board = arr.map((row) => {
  return row
    .trim()
    .split(" ")
    .map((item) => +item);
});

function solution(n, board) {
  let dp = Array.from(new Array(n), () => new Array(n).fill(false));
  dp[0][0] = true;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (dp[i][j]) {
        // 오른쪽으로 이동
        if (j + board[i][j] < n) {
          dp[i][j + board[i][j]] = true;
        }
        // 아래로 이동
        if (i + board[i][j] < n) {
          dp[i + board[i][j]][j] = true;
        }
      }
    }
  }
  return dp[n - 1][n - 1];
}

console.log(solution(+n, board) ? "HaruHaru" : "Hing");

 

코드 설명

solve()

2차원 배열 dp의 한 요소 dp[i][j]는 쩰리가 (i, j)에 도달할 수 있는지 여부를 저장한다.

 

쩰리가 처음에는 (0, 0)에 위치하여 있으므로 dp[0][0]의 값을 true로 둔다. 그런 뒤에는 오른쪽으로, 그리고 아래쪽으로 한칸씩 이동하며 현재 칸이 도달 가능한 칸이라면 현재 칸에서 이동할 수 있는 칸에도 이동 가능하다는 표시를 해준다.

 

현재 칸이 (i, j)일 때, 이동 가능한 칸이란 board[i][j]만큼 오른쪽, 또는 아래로 이동할 수 있는 칸을 말한다. 이동할 때는 행이 n 이상이거나 열이 n 이상으로 갈 수는 없다.

 

2중 for문을 모두 돌고 난 후에는 dp[n-1][n-1]에 가능 여부가 저장되어 있을테니 이 값을 반환한다.

 

문제 & 해결

2차원 배열 생성

자바스크립트로 2차원 배열을 만드는 것에 익숙하지 못해서 약간 헤맸다. 2차원 배열을 만드는 방법은 여러 가지가 있지만, 가장 직관적이고 간단한 코드라고 생각하는 아래의 코드를 찾아서 코드에 적용했다.

let dp = Array.from(new Array(n), () => new Array(n).fill(false));

이렇게 하면 dp는 n×n 2차원 배열이 된다.

입력받기

자바스크립트에서 백준 문제를 풀기 위해 입력받기 위한 코드가 약간 까다로워서 미리 구해놓은 입력 코드를 저장해두고 사용하고 있었다. 입력값은 다양한 유형으로 주어지므로 입력값을 받는 부분의 코드를 여러 개를 저장해둔 상황이었다.

 

처음에는 이 문제에서는 아래의 코드를 이용하여 입력값들을 분리하려 했다.

const [n, ...arr] = fs.readFileSync(filePath).toString().trim().split(/\s/);

let board = arr.map((row) => {
  return row.split(" ");
});

 

이렇게 n과 arr을 분리하여 사용하면 될 줄 알았는데, 이상하게 안되길래 디버깅을 하며 확인해봤더니 arr은 n×n 형태의 2차원 배열이 아니라 길이가 (n+1)×n인 1차원 배열이 되어있었다. 생각해보니 `/\s/`는 모든 공백문자, 그러니까 줄바꿈 문자 뿐만아니라 스페이스에 대해서도 `split`을 한다는 뜻이기 때문에 1차원 배열이 되었던 것이었다. 그리고 이상하게 1차원 배열도 길이가 n×n인 배열이 아니라, 한 행마다 공백문자인 요소가 하나씩 포함되어서 길이가 (n+1)×n인 1차원 배열이 되었다.

 

이 오류를 수정하기 위해 위의 코드를 다음과 같이 수정했다.

const [n, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

let board = arr.map((row) => {
  return row
    .trim()
    .split(" ")
    .map((item) => +item);
});

 

공백문자가 아닌 줄바꿈 문자를 기준으로 n과 arr을 분리하고, arr의 각 요소들에 대해 trim()으로 불필요한 공백을 없애고 문자 사이 공백을 기준으로 나눈 뒤에 각 요소를 숫자로 변환시켜주는 코드이다. 

 

이렇게 하니 처음 의도했던대로 board가 n×n 2차원 배열이 될 수 있었다.