[programmers] 리코쳇 로봇

📝 [Lv2] 리코쳇 로봇

👀 문제 설명

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

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

이 게임에서 말의 움직임은 상, 하, 좌, 우 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

 

✨ 풀이 설명

R에서 G까지 도달하는데 몇 번을 움직여야 하는지 구하는 문제이다. 포인트는,
1. 움직일 때는 D나 벽에 부딪힐 때까지 직진한다는 점
2. R이 G를 지날 수 있다는 점
3. 갔던 곳을 재방문하지 않게 해야 한다는 점
이다.

이 문제는 출발 지점이 하나인 BFS(너비 우선 탐색)로 방식으로 해결하였다.
현재 위치부터 사방으로 확인하며, 해당 위치에 D나 벽이 있는지 확인해 주었다.
만약 다음 위치가 D나 벽이라면, 현재 위치를 왔던 곳인지 확인한 후,
이미 왔던 곳이면 패스, 처음 오는 곳이라면 queue에 추가해 준 후, 왔던 곳임을 표시해 주었다.

 

먼저 필요한 것들을 선언해 주었다.
DIR은 사방으로 확인할 때 필요한 각 좌표를 담아주었고, board의 길이를 변수에 저장해 주었다.
checked는 한 번 간 위치는 다시 방문하지 않기 위해 board와 같은 크기에 0을 담은 2차원 배열을 선언해 준 것이다.
방문 배열에 표시를 하지 않게 되면, 왔던 곳을 계속해서 저장하여 불필요하게 queue가 커질 수 있다. 
start는 처음 시작할 R의 좌표를 찾아둔 것이고,
queue는 앞으로 나아갈 현재 위치들을 담아두는 곳(시작하는 위치가 지정되어 있으므로, 그 위치만 담아주었다),
L은 몇 번 움직였는지 저장하는 변수이다.

const DIR = [[-1, 0], [0, -1], [1, 0], [0, 1]];

const ROW = board.length, COL = board[0].length;

const checked = [...new Array(ROW)].map(_ => Array(COL).fill(0));

const start = board.reduce((pos, line, i) => line.indexOf('R') !== -1 ? [i, line.indexOf('R')] : pos, null);

let queue = [start], L = 0;

 

그다음 현재 위치들을 기반으로 반복문을 돌려주었다.
만약, 내부에서 도달 위치 G를 찾지 못했다면 -1을 반환해 주었다.

while (queue.length) {
...

}

return -1;

 

각 방향 별로 검색을 하면 몇 번째인지 헷갈릴 수 있으므로, tmp라는 새로운 변수를 사용해 이를 해결해 주었다.
tmp에는 현재 queue를 저장해 주고 queue를 초기화해, 한 번의 queue를 돌 때마다 L을 증가시켜 주었다.
이렇게 하면 queue에는 각 위치로부터 사방으로 갈 수 있는 다음 위치만을 저장할 수 있기 때문에, 현재가 몇 번째인지 알 수 있다.
그리고, 현재 위치가 G라면 현재까지의 진행한 횟수, L을 반환해 주었다.

const tmp = queue.slice();

queue = [];

for (const [x, y] of tmp) {

  if (board[x][y] === 'G') return L;

  for (const [dx, dy] of DIR) {
    ...

  }

}

L++;

 

그리고 나서, 반복문을 돌며 현재 위치가 board의 범위 안에서 벗어나지 않았을 때를 조건으로 while문을 돌며 다음 방향을 찾아주었다.
DIR에 저장해 둔 방향을 토대로 사방으로 1씩 움직이며 확인해 주었다.

let nx = x + dx, ny = y + dy;

while (nx >= 0 && nx < ROW && ny >= 0 && ny < COL) {

  ...  

  nx += dx;

  ny += dy;

  ...

}

 

만약, 다음 위치에 장애물 D가 있다면, 현재 위치가 이미 왔던 곳인지 확인해 준 다음, 처음 오는 곳일 경우에만 queue에 추가해 주고, 방문 배열 checked에 표시해 주었다.
다음 위치에는 장애물이 있기 때문에 더 이상 진행하지 않고, 해당 방향을 종료해 주었다.

if (board[nx][ny] === 'D') {

  if (!checked[nx - dx][ny - dy]) {

    queue.push([nx - dx, ny - dy]);

    checked[nx - dx][ny - dy] = 1;

  }

  break;

}

 

진행 방향동안 장애물이 없었고, 벽에 도달했으면 현재 위치가 이미 왔던 곳인지 확인해 준 다음, 위에서 한 것처럼 처음 오는 곳일 경우에만 queue에 추가해 주고, 방문 배열 checked에 표시해 주었다.

if ((nx < 0 || nx === ROW || ny < 0 || ny === COL) && !checked[nx - dx][ny - dy]) {

  queue.push([nx - dx, ny - dy]);

  checked[nx - dx][ny - dy] = 1;

}

 

그동안 풀었던 BFS와 조금 달랐던 점은, 좌표를 이동할 때 1칸씩 이동하는 것이 아니라는 점이었다.
그 점과 이동할 수 있는 위치가 벽의 앞, 또는 장애물 D의 앞이라는 점만 고려한다면 쉽게 해결할 수 있는 문제였다.

전체 코드는 아래에 👇

 

🕵️‍♂️ 코드

function solution(board) {

  const DIR = [[-1, 0], [0, -1], [1, 0], [0, 1]];

  const ROW = board.length, COL = board[0].length;

  const checked = [...new Array(ROW)].map(_ => Array(COL).fill(0));

  let start = board.reduce((pos, line, i) => line.indexOf('R') !== -1 ? [i, line.indexOf('R')] : pos, null);

  let queue = [start], L = 0;

  while (queue.length) {

    const tmp = queue.slice();

    queue = [];

    for (const [x, y] of tmp) {

      if (board[x][y] === 'G') return L;

      for (const [dx, dy] of DIR) {

        let nx = x + dx, ny = y + dy;

        while (nx >= 0 && nx < ROW && ny >= 0 && ny < COL) {

          if (board[nx][ny] === 'D') {

            if (!checked[nx - dx][ny - dy]) {

              queue.push([nx - dx, ny - dy]);

              checked[nx - dx][ny - dy] = 1;

            }

            break;

          }

          nx += dx;

          ny += dy;

          if ((nx < 0 || nx === ROW || ny < 0 || ny === COL) && !checked[nx - dx][ny - dy]) {

            queue.push([nx - dx, ny - dy]);

            checked[nx - dx][ny - dy] = 1;

          }

        }

      }

    }

    L++;

  }

  return -1;

}