프로그래머스 / Level 2 , 깊이/너비 우선 탐색(DFS/BFS) , 게임 맵 최단거리 자바스크립트 , JS

프로그래머스 / Level 2 , 깊이/너비 우선 탐색(DFS/BFS) , 게임 맵 최단거리 자바스크립트 , JS

 

 

 

 

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/1844#qna

프로그래머스

 

 

 

 

 

 

 

 

 

정답

 

 

1) visited  최초 방문 처리로 풀기 

function solution(maps) {
  let answer = 0;
  let [N, M] = [maps.length, maps[0].length];
  let dr = [
    [0, 1],
    [1, 0],
    [-1, 0],
    [0, -1],
  ];
  let dq = [[1, 0, 0]];
  let visited = Array.from(Array(N), () => Array(M).fill(false));
  visited[0][0] = true;
  while (dq.length !== 0) {
    let [Z, X, Y] = dq[0];
    dq = dq.splice(1);
    for (let i of dr) {
      let [mx, my] = [X + i[0], Y + i[1]];
      if (mx >= N || mx < 0 || my >= M || my < 0) continue;
      else {
        if (!visited[mx][my] && maps[mx][my] === 1) {
          dq.push([Z + 1, mx, my]);
          visited[mx][my] = true;
          if (mx === N - 1 && my === M - 1) {
            answer = Z + 1;
            break;
          }
        }
      }
    }
  }
  return answer !== 0 ? answer : -1;
}

 

 

 

 

2) dist 최소 거리 찾으면서 풀기

 

function solution(maps) {
  let [N, M] = [maps.length, maps[0].length];
  let dr = [
    [0, 1],
    [1, 0],
    [-1, 0],
    [0, -1],
  ];
  let dq = [[0, 0]];
  let dist = Array.from(Array(N), () => Array(M).fill(Infinity));
  dist[0][0] = 1;
  while (dq.length !== 0) {
    let [X, Y] = dq[0];
    dq = dq.splice(1);
    for (let i of dr) {
      let [mx, my] = [X + i[0], Y + i[1]];
      if (mx >= N || mx < 0 || my >= M || my < 0) continue;
      else {
        if (dist[mx][my] > dist[X][Y] + 1 && maps[mx][my] === 1) {
          dq.push([mx, my]);
          dist[mx][my] = dist[X][Y] + 1;
        }
      }
    }
  }
  return dist[N - 1][M - 1] !== Infinity ? dist[N - 1][M - 1] : -1;
}