프로그래머스 LEVEL 2(리코쳇 로봇)

사용 언어 : javascript
해결 날짜 : 2023-05-02
해결 방법 :
- bfs를 통해 문제 해결
  - 계산에 용이하도록 board 변경하며 R, G 위치 저장
  - bfs를 수행하되, 벽이나 장애물(D)를 만나기 전까지 그 방향으로 쭉 이동
    - 방문 여부도 체크하여 큐에 이미 방문한 위치가 들어가지 않도록 최적화
    - 큐에 count도 추가하여 움직임 계산
  - 현재 위치가 G일 경우 answer 최솟값으로 업데이트
회고 :
- 벽이나 장애물을 만나기 전까지 쭉 이동하는 로직을 더 간결하게 작성할 수 있을 것 같다는 생각이 든다..
- visited를 두 번 체크하는 것과 nextX, nextY 더하는 로직이 두 번 작성된 것 같아서 조금만 더 생각해보면 읽기 편한 코드가 될 듯..?

코드

function solution(board) {
  let answer = Infinity;
  const positions = {};

  board = board.map((b, i) =>
    b.split('').map((v, j) => {
      if (v === '.') return 0;
      else if (v === 'D') return 1;
      else {
        positions[v] = [i, j];
        return 0;
      }
    }),
  );

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

  const maxWidth = board[0].length,
    maxHeight = board.length;

  const visited = Array.from({ length: maxHeight }, () =>
    Array.from({ length: maxWidth }, () => false),
  );

  const q = [[...positions.R, 0]];

  while (q.length) {
    const [x, y, count] = q.shift();

    visited[x][y] = true;

    if (x === positions.G[0] && y === positions.G[1]) {
      answer = Math.min(answer, count);
      continue;
    }

    moves.forEach((move, i) => {
      let [nextX, nextY] = [x + move[0], y + move[1]];

      if (
        nextX < 0 ||
        nextY < 0 ||
        nextX >= maxHeight ||
        nextY >= maxWidth ||
        board[nextX][nextY] ||
        visited[nextX][nextY]
      ) {
        return;
      }

      while (
        nextX + move[0] >= 0 &&
        nextY + move[1] >= 0 &&
        nextX + move[0] < maxHeight &&
        nextY + move[1] < maxWidth &&
        board[nextX + move[0]][nextY + move[1]] !== 1
      ) {
        nextX += move[0];
        nextY += move[1];
      }

      if (visited[nextX][nextY]) {
        return;
      }

      q.push([nextX, nextY, count + 1]);
    });
  }

  return answer === Infinity ? -1 : answer;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges