BFS 문제 풀이 ( feat: 게임 맵 최단거리 프로그래머스 )

단지 번호 붙이기

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

문제 설명
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

제한 사항
maps는 n x m 크기의 게임 맵 상태가 들어 있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
n과 m은 서로 같을 수도, 다를 수도 있지만 n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대 팀 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

풀이

• 주어진 maps에 맞춰 행과 열의 개수를 정의
• BFS 알고리즘을 이용해 매 칸 이동 시 상하좌우를 체크하여 이동
• 최단 거리 완성

function solution(maps) {
  const x = maps.length; // 행
  const y = maps[0].length; // 열

  // 상하좌우
  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  function bfs() {
    // 시작 위치 (0, 0), 이동 거리 1
    const queue = [[0, 0, 1]];
    maps[0][0] = 0;
    while (queue.length > 0) {
      let [row, col, dist] = queue.shift();
      // 도착 시 리턴
      if (row == x - 1 && col == y - 1) {
        return dist;
      }
      for (let [r, c] of directions) {
        let nRow = row + r;
        let nCol = col + c;
        // 새로운 위치가 맵 내에 있고, 벽이 아니어야 이동 가능
        if (
          nRow >= 0 &&
          nRow < x &&
          nCol >= 0 &&
          nCol < y &&
          maps[nRow][nCol] === 1
        ) {
          queue.push([nRow, nCol, dist + 1]);
          // 방문한 위치를 0으로 표시
          maps[nRow][nCol] = 0;
        }
      }
    }
    return -1;
  }
  return bfs();
}

정리

• BFS를 이용해 문제를 풀 수 있었다.
• 그런데 효율성 측면에서 ===가 있을 때 오류가 났고, ==으로 바꾸니 작동했다. 타입을 정확히 비교하는 게 맞는 게 아닌가 하는 생각이 든다.
• 명확한 이유를 아직 찾지 못했다.