[Lv.2] 리코쳇로봇 - JavaScript

문제

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

프로그래머스

 

풀이

- 최단거리를 구하는 문제이므로 BFS를 이용한다.

- 단순 너비우선과 달리 4방향을 탐색하면서 while문을 사용하여 미끄러져야 한다.

- 다른 방향으로 미끄러질 수 있으므로 벽에 부딪히거나 장애물을 만났을때 멈춘 좌표만 방문처리를 해주자.

 

코드

function solution(board) {
  var answer = 0;
  const rows = board.length;
  const cols = board[0].length;

  const BFS = (si, sj) => {
    let queue = [];
    queue.push([si, sj, 0]);

    while (queue.length) {
      const [i, j, cnt] = queue.shift();
      visited[i][j] = true;

      // BFS이므로 처음 리턴한 값이 최단 거리
      if (board[i][j] === "G") {
        answer = cnt;
        return;
      }

      // 4방향 탐색하기 & 미끄러지기
      for ([di, dj] of [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0],
      ]) {
        let ni = i + di;
        let nj = j + dj;
        // 벽과 장애물에 닿지 않을 때까지 미끄러진다
        while (
          0 <= ni &&
          ni < rows &&
          0 <= nj &&
          (nj < cols) & (board[ni][nj] !== "D")
        ) {
          ni += di;
          nj += dj;
        }
        // 이미 닿은 상태이므로 한칸 이전으로 되돌려주기
        ni -= di;
        nj -= dj;
        // 방문하지 않은 위치일때
        if (!visited[ni][nj]) {
          // 큐에 삽입
          queue.push([ni, nj, cnt + 1]);
        }
      }
    }
  };

  // 방문처리를 할 배열 생성
  let visited = Array(rows)
    .fill()
    .map(() => Array(cols).fill(false));
  // 시작점 찾기
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] === "R") {
        BFS(i, j);
        break;
      }
    }
  }

  // answer가 여전히 0 이라면 방법이 없다는 뜻 이므로 -1 리턴 
  return answer ? answer : -1;
}