프로그래머스 - Lv.2 리코쳇 로봇 (BFS) node.js

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

해당 문제는 너비우선탐색 알고리즘인 BFS에 대한 이해가 되어 있다면 시간을 들여 충분히 해결할 수 있는 문제다.

타 BFS 알고리즘 문제와 달리, 다음 경로가 '게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 이동'한다는 점만 주의하면 된다.

 

문제 풀이 방식은 다음과 같다.

- 주어진 board 에서 시작지점과 도착지점을 찾는다.

- BFS 알고리즘 구현하되, 이때 이동하는 방향에 따라 미끄러져 이동했을 때 도달할 수 있는 다음 위치를 반환하는 함수를 구현한다.

 

전체 소스 코드

function solution(board) {
  const Y = board.length,
    X = board[0].length;

  let start, end;

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] == "R") start = [i, j];
      if (board[i][j] == "G") end = [i, j];
    }
  }

  return BFS(board, start, end, X, Y);
}

function BFS(board, start, end, X, Y) {
  // 방문 기록
  const visited = Array.from({ length: Y }, () => {
    return Array.from({ length: X }, () => 0);
  });
  
  // queue의 원소는 [y좌표,x좌표,거리]를 담는다.
  const queue = [start.concat(1)];
  let queueIdx = 0;
  
  // 이동 방향
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  
  // 위치 검증 함수
  const verify = (x, y) => {
    return 0 <= x && x < X && 0 <= y && y < Y && board[y][x] != "D";
  };

  // 미끄러져 이동했을 때 다음 위치를 반환하는 함수
  const moving = (location, direction) => {
    const [y, x] = location;
    const [dy, dx] = direction;
    let i = 1;
    let nextLocation = [y, x];
    while (true) {
      const [ny, nx] = [dy * i + y, dx * i + x];
      if (!verify(nx, ny)) break;
      else nextLocation = [ny, nx];
      i++;
    }

    const [ny, nx] = nextLocation;
    if ((nx == x && ny == y) || visited[ny][nx]) return false;
    else return [ny, nx];
  };

  while (queueIdx < queue.length) {
    const [y, x, dist] = queue[queueIdx++];

    // 이동한 위치가 도착지점이라면 거리 -1 을 리턴
    const [ty, tx] = end;
    if (x == tx && y == ty) return dist - 1;
    
    // 다음 이동 방향에 따라 moving 함수 실행
    directions.forEach((el) => {
      const next = moving([y, x], el);
      if (next) {
        const [ny, nx] = next;
        visited[ny][nx] = dist + 1;
        queue.push([ny, nx, dist + 1]);
      }
    });
  }
  
  // 도착지점 도달하지 못하고 queue의 원소를 모두 사용한 경우 -1 리턴
  return -1;
}