Programmers / Level 2 / 리코쳇 로봇 / JS

문제 간단설명

시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임이다. 말은 상, 하, 좌, 우 4방향 중 한 방향으로만 움직일 수 있으며, 게임판 맨 끝이나 장애물에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 한다.

• '.' : 빈 공간
• 'R' : 로봇의 처음 위치
• 'D' : 장애물의 위치
• 'G' : 목표지점 

게임판은 위 4가지로 구성되어 있으며, 최소 몇 번을 이동해야 하는지 반환하면 된다. 만약 도달할 수 없다면 -1을 반환하면 된다.

 

제한 사항

• 3 <= board의 길이 <= 100
  • 3 <= board의 원소의 길이 <= 100
  • board의 원소의 길이는 모두 동일하다.
  • 'R'과 'G'는 한 번씩 등장한다.

 

성공 코드

function solution(board) {
  const dr = [-1, 1, 0, 0];
  const dc = [0, 0, -1, 1];

  const EMPTY = '.';
  const START = 'R';
  const OBSTACLE = 'D';
  const GOAL = 'G';

  const totalRow = board.length;
  const totalCol = board[0].length;

  /**
   * 행과 열이 유효한 인덱스인지 판단해서 boolean 값으로 반환하는 함수
   * @param {number} row 행
   * @param {number} col 열
   * @returns 유효한 인덱스라면 true, 아니라면 false를 반환한다.
   */
  const isValid = (row, col) => {
    if (row < 0 || row >= totalRow) {
      return false;
    }
    if (col < 0 || col >= totalCol) {
      return false;
    }

    return true;
  };

  /**
   * 시작점이 되는 행,열과 방향을 인자로 받아서 해당 방향으로 끝까지 간 위치를 반환하는 함수
   *
   * @param {number} row 행
   * @param {number} col 열
   * @param {number} dir 방향
   * @returns 끝까지 간 위치를 반환한다.
   */
  const move = (row, col, dir) => {
    let nr = row;
    let nc = col;

    while (true) {
      // 범위를 벗어난다면 멈춘다.
      if (isValid(nr, nc) === false) {
        break;
      }
      // 장애물이 있다면 멈춘다.
      if (board[nr][nc] === OBSTACLE) {
        break;
      }

      nr += dr[dir];
      nc += dc[dir];
    }

    // 마지막 반복에서 갈 수 없는 칸까지 갔기 때문에 한 칸 빼준다.
    return [nr - dr[dir], nc - dc[dir]];
  };

  /**
   * BFS를 이용해 몇 번 이동했는지 반환하는 함수
   *
   * @param {number} row 행
   * @param {number} col 열
   * @returns 몇 번 이동했는지 반환한다.
   */
  const bfs = (row, col) => {
    const queue = [[row, col, 0]];
    const visited = Array.from({ length: totalRow }, () =>
      Array.from({ length: totalCol }, () => false)
    );

    while (queue.length > 0) {
      const [curRow, curCol, count] = queue.shift();

      // 목표지점이라면 이동한 횟수를 반환한다.
      if (board[curRow][curCol] === GOAL) {
        return count;
      }

      for (let d = 0; d < 4; d++) {
        const [nr, nc] = move(curRow, curCol, d);

        if (visited[nr][nc] === true) {
          continue;
        }

        visited[nr][nc] = true;
        queue.push([nr, nc, count + 1]);
      }
    }

    return -1;
  };

  for (let i = 0; i < totalRow; i++) {
    for (let j = 0; j < totalCol; j++) {
      if (board[i][j] === START) {
        return bfs(i, j);
      }
    }
  }
}

 

흔한 BFS 형식의 문제에서 '범위를 벗어나거나 부딫힐 때 까지 이동' 조건을 추가한 문제이다.

따라서, 저 이동을 하는 로직을 따로 함수로 빼 구현하였다. 주의할 점은 장애물이나 범위를 벗어난 칸에 도달했을 경우에 반복문이 멈추는것이기 때문에, 그 전의 칸을 반환해야 한다.

 

흔히 bfs나 dfs 문제를 풀 때, 이동하게 되면 dr, dc 혹은 dx, dy를 정의해놓고 방향을 탐색하는데, 함수의 인자로 받는 방향(dir)은 이동 방향에 해당하는 인덱스를 넣어주었다.