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

풀이 과정

최단거리 BFS

• 다음 이동 위치가 게임판을 벗어나거나 D(장애물)일 때까지 이동 및 이동 횟수 +1
• 이동 후에 현재 위치가 G(목표 위치)면 종료

코드

function solution(board) {
  const [r, c] = [board.length, board[0].length];
  const dy = [-1, 0, 1, 0]; // 위 오른 아래 왼
  const dx = [0, 1, 0, -1];

  const q = [];
  for (let i = 0; i < r; ++i) {
    for (let j = 0; j < c; ++j) {
      if (board[i][j] === 'R') {
        q.push([i, j, 0]);
        break;
      }
    }
    if (q.length) break;
  }

  const visited = Array(r)
    .fill(0)
    .map(() => Array(c).fill(false));
  while (q.length) {
    const [y, x, cnt] = q.shift();
    if (board[y][x] === 'G') return cnt;
    visited[y][x] = true;
    for (let i = 0; i < 4; ++i) {
      let ny = y;
      let nx = x;
      while (true) {
        const nny = ny + dy[i];
        const nnx = nx + dx[i];
        if (
          nny < 0 ||
          nny >= r ||
          nnx < 0 ||
          nnx >= c ||
          board[nny][nnx] === 'D'
        )
          break;
        ny = nny;
        nx = nnx;
      }
      if (ny === y && nx === x) continue;
      if (visited[ny][nx]) continue;
      q.push([ny, nx, cnt + 1]);
    }
  }
  return -1;
}

🦾

우와 한번에 통과했다! 정말 뿌듯하다 😁
처음에 문제 이해가 좀 어려웠는데, G를 만나면 멈추는 게 아니라 R에서 출발하듯이 그냥 통과해서 지나간다는 걸 염두해야 한다.