[프로그래머스] 리코쳇 로봇

문제

리코쳇 로봇

https://school.programmers.co.kr/learn/courses/30/lessons/169199

 

 

예시 코드

function solution(board) {
  const ROBOT = "R";
  const GOAL = "G";
  const OBSTACLE = "D";

  const [n, m] = [board.length, board[0].length];
  const start = [];
  const goal = [];

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (board[i][j] === ROBOT) start.push(i, j);
      if (board[i][j] === GOAL) goal.push(i, j);
    }
  }

  return bfs(start, goal);

  function bfs(start, goal) {
    const dx = [0, -1, 0, 1];
    const dy = [1, 0, -1, 0];
    
    const [sx, sy] = start;
    const [gx, gy] = goal;
    const visited = Array.from({ length: n }, () => Array(m).fill(false));
    const queue = new Queue();
    queue.enqueue([sx, sy, 0]);
    visited[sx][sy] = true;

    while (!queue.isEmpty()) {
      const [cx, cy, cnt] = queue.dequeue();
      if (cx === gx && cy === gy) return cnt;

      for (let i = 0; i < 4; i++) {
        const [nx, ny] = getNextPosition(cx, cy, dx[i], dy[i]);

        if (visited[nx][ny]) continue;
        visited[nx][ny] = true;

        queue.enqueue([nx, ny, cnt + 1]);
      }
    }

    return -1;
  }

  function getNextPosition(x, y, dx, dy) {
    while (true) {
      const [nx, ny] = [x + dx, y + dy];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) break;
      if (board[nx][ny] === OBSTACLE) break;
      [x, y] = [nx, ny];
    }

    return [x, y];
  }
}

 

풀이

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지를 구하는 문제입니다.

 

일반적인 미로 찾기 문제와 비슷하나 한 가지가 다릅니다.

여기서는 게임판 위 장애물이나 게임판 가장자리까지 부딪힐 때까지 미끄러져 움직이는 것을 한 번의 이동으로 정의합니다.

 

최소한의 이동 횟수를 구해야하므로 BFS를 사용합니다.

이동 관련 로직은 getNextPosition 함수에 구현했습니다.

 

board의 크기가 n * m일 경우, 시간 복잡도는 O(n * m)이 됩니다.