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

function solution(maps) {
  let dy = [1, 0, -1, 0];
  let dx = [0, 1, 0, -1];
  let destion = [maps.length - 1, maps[0].length - 1];
  let answer = 9999999999999;

  function DFS(y, x, num) {
    if (y === destion[0] && x === destion[1]) {
      answer = Math.min(num, answer);
      console.log(answer);
    } else {
      for (let i = 0; i < dx.length; i++) {
        let ny = y + dy[i];
        let nx = x + dx[i];
        if (
          ny >= 0 &&
          nx >= 0 &&
          ny < maps.length &&
          nx < maps[0].length &&
          maps[ny][nx] === 1
        ) {
          maps[ny][nx] = 0;
          num++;
          DFS(ny, nx, num);
          maps[ny][nx] = 1;
          num--;
        }
      }
    }
  }

  DFS(0, 0, 0);

  if (answer === 9999999999999) {
    return -1;
  } else {
    return answer + 1;
  }
}

처음에 DFS로 풀어보았다.

나는 개인적으로는 DFS가 더 편하기 떄문에 DFS로 해결을 해보았지만 역시나 최단거리를 구하는 문제이기 떄문에 효율적인 측면에서 실패가 되었다.

즉 BFS를 통해서 해결을 해야 한다는 것이다.

function solution(maps) {
  let answer = 1;
  let queue = [];
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  const n = maps.length;
  const m = maps[0].length;

  queue.push([0, 0]);
  maps[0][0] = 0;

  while (queue.length > 0) {
    let size = queue.length;

    for (let i = 0; i < size; i++) {
      let [x, y] = queue.shift();

      for (let j = 0; j < 4; j++) {
        let nx = x + dx[j];
        let ny = y + dy[j];

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

  return -1;
}

BFS는 그렇게 익숙하지가 않아서 작성을 하는데에 조금 시간이 소요 되었습니다.

기본적으로 검증 하는 과정은 DFS와 동일한데 이상하게 shift()를 통해서 값을 뺴오는 작업은 왜이리 익숙하지가 않는지...ㅠㅠ