[프로그래머스] 게임 맵 최단거리(Javascript)

코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

알고리즘 : bfs

 

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

  let vis = new Array(n).fill().map((v) => new Array(m).fill(0));


  let dx = [0, 1, 0, -1];
  let dy = [1, 0, -1, 0];

  const bfs = (x, y) => {
    let queue = [];
    vis[x][y] = 1;
    queue.push([x, y]);
    while (queue.length) {
      let [cx, cy] = queue.shift();
      for (let dir = 0; dir < 4; dir++) {
        let nx = cx + dx[dir];
        let ny = cy + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (input[nx][ny] === 0 || vis[nx][ny] !== 0) continue;
        vis[nx][ny] = vis[cx][cy] + 1;
        queue.push([nx, ny]);
      }
    }
  };

  bfs(0, 0);
  return vis[n - 1][m - 1] ? vis[n-1][m-1]:-1;
}