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

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

프로그래머스

 

문제 설명

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

---

제한 사항

• 3 ≤ board의 길이 ≤ 100
  • 3 ≤ board의 원소의 길이 ≤ 100
  • board의 원소의 길이는 모두 동일합니다.
  • 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
  • "R"과 "G"는 한 번씩 등장합니다.

---

입출력 예

board	result
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]	7
[".D.R", "....", ".G..", "...D"]	-1

 

 

로직

1. 시작점, 목표지점을 구한다
2. isVisited배열에서 시작점은 true로 초기화
3. 시작점에서 4가지 방향을 탐색한다
   1. 탐색할때 'D'나 배열의 끝에 다다를때까지 while을 돌린다
4. 탐색 중 방문한 적이 없는 갈 수 있는 위치만 queue에 넣는다
   1. 이미 방문한 적이 있는 곳이면 또 다시 방향을 탐색해도 loop된다.
5. queue에 있는 위치중 목표지점에 도달하면 time을 리턴한다.

 

function solution(board) {
  const dR = [-1, 0, 1, 0];
  const dC = [0, 1, 0, -1];
  const maxR = board.length;
  const maxC = board[0].length;
  let start = {};
  let target = {};

  function isMovable(r, c) {
    if (r < 0 || r >= maxR || c < 0 || c >= maxC) {
      return false;
    } else if (board[r][c] === "D") {
      return false;
    }
    return true;
  }

  // 시작점, 목표위치 찾기
  for (let r = 0; r < maxR; r++) {
    for (let c = 0; c < maxC; c++) {
      if (board[r][c] === "R") start = { r, c };
      if (board[r][c] === "G") target = { r, c };
    }
  }

  const isVisited = Array.from({ length: maxR }, () =>
    Array.from({ length: maxC }, () => false)
  );
  isVisited[start.r][start.c] = true;
  const queue = [{ r: start.r, c: start.c, step: 0 }];

  while (queue.length) {
    const { r, c, step } = queue.shift();
    // 타겟을 찾음
    if (r === target.r && c === target.c) {
      return step;
    }

    // 4가지 방향 찾기
    for (let i = 0; i < 4; i++) {
      let currR = r;
      let currC = c;
      let nextR = currR + dR[i];
      let nextC = currC + dC[i];
      // 범위안에서 D를 만나거나 끝에 다다를 때까지 직진
      while (isMovable(nextR, nextC)) {
        currR = nextR;
        currC = nextC;
        nextR += dR[i];
        nextC += dC[i];
      }
      if (!isVisited[currR][currC]) {
        isVisited[currR][currC] = true;
        queue.push({ r: currR, c: currC, step: step + 1 });
      }
    }
  }
  return -1;
}