프로그래머스 게임 맵 최단거리 자바스크립트

문제 링크

- 내 풀이

function solution(maps) {
  let n = maps.length;
  let m = maps[0].length;

  let dir = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];

  // 행, 렬, 움직인 횟수 배열에 담아주기
  let moveAndPos = [0, 0, 1];

  let queue = [];

  queue.push(moveAndPos);

  while (queue.length) {
    let [x, y, move] = queue.shift();

    // 행과 렬이 게임 맵의 끝 위치와 같다면 move 값 리턴
    if (x === n - 1 && y === m - 1) {
      return move;
    }

    for (let i = 0; i < 4; i++) {
      let nx = x + dir[i][0];
      let ny = y + dir[i][1];

      if (nx >= 0 && ny >= 0 && nx < n && ny < m && maps[nx][ny] !== 0) {
        // 방문 표시를 해줌으로써 효율성을 높임
        maps[nx][ny] = 0;

        // move 값을 높여서 queue 에 담아줌
        queue.push([nx, ny, move + 1]);
      }
    }
  }

  return -1;
}

처음 접해본 BFS 문제였다.

BFS는 깊이 우선 탐색으로써, queue 자료구조를 이용하여 푼다.

queue에 위치와 움직인 move값을 빼주고 dir 배열에 반복문을 돌았을때 조건에 맞는 경로를 찾았다면

방문처리를 해주고 queue에 그 값을 다시 담아준다.