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

문제 설명

리코쳇 로봇 보드게임에서 말이 목표 위치에 도달하기 위한 최소 이동 횟수를 구하세요.
말은 상, 하, 좌, 우로 이동하며, 장애물 또는 게임판 가장자리에 부딪힐 때까지 미끄러집니다.

제한 사항

• 보드 크기: 3 ≤ n, m ≤ 100
• "R"(로봇 시작 위치), "G"(목표 지점)은 각각 한 번 등장합니다.
• "."(빈 공간), "D"(장애물)

---

해결 방법

알고리즘: DP

1. BFS를 통한 탐색 진행
   시작 위치에서 목표 지점까지 이동하며 최소 이동 횟수를 기록합니다.
2. DP 배열 활용
   각 위치에서의 최소 이동 횟수를 dp[y][x]에 저장하며 경로를 최적화합니다.
3. 이동 구현
   현재 위치에서 상, 하, 좌, 우로 부딪힐 때까지 이동 후, 새로운 위치에서 BFS 탐색을 이어갑니다.

---

시간 복잡도

• BFS 탐색: O(n×m)
  모든 칸을 한 번씩 방문하며 이동 경로를 탐색합니다.

---

구현 코드

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  push(value) {
    const newNode = new Node(value);

    if (this.size === 0) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }

    ++this.size;
  }

  pop() {
    if (this.size === 0) {
      return null;
    }

    const value = this.front.value;
    this.front = this.front.next;
    --this.size;

    if (this.size === 0) {
      this.rear = null;
    }

    return value;
  }
}

function solution(board) {
  let dp = [];
  const q = new Queue();
  const newBoard = board.map((item) => item.split(""));
  const moveY = [0, 1, 0, -1];
  const moveX = [1, 0, -1, 0];

  for (let i = 0; i < newBoard.length; ++i) {
    const temp = [];
    for (let j = 0; j < newBoard[0].length; ++j) {
      if (newBoard[i][j] === "R") {
        q.push({ y: i, x: j, c: 0 });
        temp.push(0);
      } else {
        temp.push(Infinity);
      }
    }
    dp.push(temp);
  }

  while (q.size > 0) {
    const { y, x, c } = q.pop();

    for (let i = 0; i < 4; ++i) {
      let cy = y;
      let cx = x;

      while (
        cy + moveY[i] >= 0 &&
        cx + moveX[i] >= 0 &&
        cy + moveY[i] < newBoard.length &&
        cx + moveX[i] < newBoard[0].length &&
        newBoard[cy + moveY[i]][cx + moveX[i]] !== "D"
      ) {
        cy += moveY[i];
        cx += moveX[i];
      }

      if (newBoard[cy][cx] === "G") {
        return c + 1;
      }

      if (c + 1 < dp[cy][cx]) {
        dp[cy][cx] = c + 1;
        q.push({ y: cy, x: cx, c: c + 1 });
      }
    }
  }

  return -1;
}