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) 위치에 있습니다.

풀이

• 주어진 맵스에 맞춰 행열의 갯수를 정의
• 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를 이용해 문제를 풀 수 있었다.
• 그런데 , 효율성 측면에서 === 이 있을 때 오류였고 ==으로 바꾸니 작동했다. 타입을 정확히 비교하는게 맞는게 아닌가한 생각이 든다.
• 명확한 이유를 아직 찾지 못했다.