[JS] 프로그래머스 - 게임 맵 최단거리

📌  문제

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
 

💡  아이디어

최단거리 -> BFS 
처음에 visited 배열을 만들어서 방문 여부를 표시해줬는데 계속 통과를 못했다..
이유는 이차원 배열 선언을 잘못 했기 때문..

const visited = new Array(n).fill(new Array(m).fill(false));
// 이런 식으로 하면 map이 안돌아서 당연히 이차원 배열이 잘못 선언되는데 왜 이렇게 했지

이차원 배열도 고치고 다시 시도했지만 시간초과 -> visited 배열을 만드는 게 효율적이지 X
visited 배열을 만들지 않고 그냥 maps 자체를 0으로 바꿔주면 어차피 못가기 때문에 visited 배열을 true로 바꿔주는 것과 같은 역할
 

✏️  풀이

// 시간초과 코드

function solution(maps) {
  var answer = 0;
  const n = maps.length;
  const m = maps[0].length;
  const queue = [[0, 0, 1]];
  const visited = Array.from(Array(n),() => Array(m).fill(0));
  visited[0][0] = true;
  const dx = [0, 0, -1, 1];
  const dy = [1, -1, 0, 0];

  while(queue.length) {
    let [x, y, count] = queue.shift();
    if(x === n-1 && y === m-1) return count;
    
    for(let i=0; i<4; i++){
      const moveX = x + dx[i];
      const moveY = y + dy[i];

      if(moveX >= 0 && moveX < n && moveY >= 0 && moveY < m) {
        if(!visited[moveX][moveY] && maps[moveX][moveY] === 1) {
          visited[moveX][moveY] = false;
          queue.push([moveX, moveY, count + 1]);
        }
      }
    }
  }
  return -1;
}

// 정답 코드
function solution(maps) {
  var answer = 0;
  const n = maps.length;
  const m = maps[0].length;
  const queue = [[0, 0, 1]];
  const dx = [0, 0, -1, 1];
  const dy = [1, -1, 0, 0];
  if(maps[n-1][m-2] === 0 && maps[n-2][m-1] === 0) return -1;

  while(queue.length) {
    let [x, y, count] = queue.shift();
    if(x === n-1 && y === m-1) return count;
    
    for(let i=0; i<4; i++){
      const moveX = x + dx[i];
      const moveY = y + dy[i];

      if(moveX >= 0 && moveX < n && moveY >= 0 && moveY < m) {
        if(maps[moveX][moveY] === 1) {
          maps[moveX][moveY] = 0;
          queue.push([moveX, moveY, count + 1]);
        }
      }
    }
  }
  return -1;
}