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

 

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

프로그래머스

접근 방법

이 문제는 DFS, BFS로 푸는 것이 가능하지만 최단거리를 구하는 문제이기 때문에 DFS로 풀 경우에는 최단거리로 도착하였음에도 계속해서 경로를 찾기 때문에 런타임 오류가 발생한다. 그렇기 때문에 이렇게 최단거리를 구하는 문제에서는 BFS로 푸는 것이 효율적인 풀이 방법이다.

• 현재 위치에서 이동이 가능한 방향을 queue에 저장한다.
• 왔던 경로로 돌아가는 것을 막아야 한다.
• 목적지에 도착하였다면 더 이상 경로 탐색을 중지한 뒤 값을 반환한다.
• 모든 경로를 방문하였음에도 목적지에 도착하지 못했다면 -1을 반환하다.

풀이

풀기전 필요한 요소 세팅

시작지점부터 현재 경로까지의 거리를 저장해 둘 배열(check)을 생성해준다.
이때 배열은 주어진 지도와 동일한 배열로 생성해줘야 한다.
그리고 상하좌우로 이동하기 위한 배열을 생성해줬다.
그후 시작지점을 0으로 바꾼 후에 해당 위치의 배열을(check) 1증가시켜준다.

이떄 주의해야 할점은 목적지의 좌표가 (4,3)이라고 가정한다면 우리는 이를 배열로 나타내기 위해 [4,3] 이렇게 생각하기 쉽다.
하지만 좌표를 배열로 표시할 때는 [3,4]로 표시해야 우리가 생각하는 (4,3)의 좌표와 동일한 것이다.
이점만 유의하며 문제를 풀어나가면 된다.
좌표(x,y) => 배열 [y,x]

 let xL = arr[0].length;
  let yL = arr.length;
  // x,y  => [y,x]
  const check = Array.from({ length: yL }, () => Array.from({ length: xL }, () => 0));
  const moveX = [-1, 0, 1, 0];
  const moveY = [0, 1, 0, -1];
  const queue = [];
  queue.push([0, 0]);
  arr[0][0] = 0;
  check[0][0] = 1;
/* 
예시
check
[
  [1,0,0,0],
  [0,0,0,0],
  [0,0,0,0],
]
map
[
  [0,0,0,0],
  [1,0,0,0],
  [1,1,1,1],
]
*/

탐색이 가능한 노드의 좌표 계산 코드 작성

이제 탐색이 가능한 노드의 좌표를 구하는 코드를 작성해주면 된다. 
먼저 현재의 위치값을 제대로 계산하는지를 구해보자.
이후 조건을 통해 우리에게 실제로 필요한 값만 출력하게 해주면 된다.
먼저 배열의 범위를 조건에 넣어준 후에 마지막에 조건으로 지도(arr)에 우리가 움직일 값이 1인지를 확인하는 조건을 넣어줘야한다.
이때 지도의 값이 1인지를 확인하는 조건의 위치에 제일 마지막이 아니라면 오류가 발생하기 때문에 무조건 마지막에 넣어주어야 한다.
그럼 모든 조건을 충족한 x,y값이 출력되게 된다.

while (queue.length) {
    let el = queue.shift();
    for (let i = 0; i < 4; i++) {
      let curX = el[0] + moveX[i];
      let curY = el[1] + moveY[i];
      if (curX >= 0 && curX <= xL - 1 && curY >= 0 && curY <= yL - 1 && arr[curY][curX] === 1) {
        console.log(curX,curY)
      }
    }
  }

최단거리 구하는 코드 작성

이제 queue에 움직이는 것이 가능한 좌표를 실제로 넣어주는 과정이 필요하다.
queue에 움직일 좌표를 넣어주는 것과 동시에 이전 위치로 돌아가는 것을 막기위해 해당 값을 0으로 바꿔줘야 한다.
만약 이때 값을 바꿔주지 않고, shift하면서 값을 빼주게 된다면 동일한 좌표의 값이 두번이 들어가게 되기 때문에 꼭 queue에 넣어주면서 값을 0으로 변경해줘야 한다.
그후 check배열에 지금까지의 경로 거리를 현재 좌표값에 저장해주자.
이렇게만 작성한다면 모든 경로를 다 돌게 되기 때문에 목적지에 도착하면 종료하는 조건도 추가해주자.

while (queue.length) {
    let el = queue.shift();
    for (let i = 0; i < 4; i++) {
      let curX = el[0] + moveX[i];
      let curY = el[1] + moveY[i];
      if (curY === yL - 1 && curX === xL - 1) {
        return check[el[1]][el[0]] + 1;
      }
      if (curX >= 0 && curX <= xL - 1 && curY >= 0 && curY <= yL - 1 && arr[curY][curX] === 1) {
        arr[curY][curX] = 0;
        queue.push([curX, curY]);
        check[curY][curX] = check[el[1]][el[0]] + 1;
      }
    }
  }
/* 
예시
check
[
  [1,0,0,0],
  [2,0,0,0],
  [3,4,0,0],
]
map
[
  [0,0,0,0],
  [0,0,0,0],
  [0,0,1,1],
]
*/

이렇게 주어진 노드를 탐색하며 목적지에 도착하면 while문에서 바로 정답을 반환하며 최단거리를 구하게 되고,
모든 노드를 탐색하였음에도 불구하고 목적지에 도착하지 못했다면 해당 queue의 길이가 0이 되며 while문이 끝나게 되고, 도착하지 못하였기 때문에 -1을 반환하게 된다.

최종 코드

function solution(arr) {
  let xL = arr[0].length;
  let yL = arr.length;
  const check = Array.from({ length: yL }, () => Array.from({ length: xL }, () => 0));

  const moveX = [-1, 0, 1, 0];
  const moveY = [0, 1, 0, -1];
  const queue = [];
  queue.push([0, 0]);
  arr[0][0] = 0;
  check[0][0] = 1;

  while (queue.length) {
    let el = queue.shift();
    for (let i = 0; i < 4; i++) {
      let curX = el[0] + moveX[i];
      let curY = el[1] + moveY[i];
      if (curY === yL - 1 && curX === xL - 1) {
        return check[el[1]][el[0]] + 1;
      }
      if (curX >= 0 && curX <= xL - 1 && curY >= 0 && curY <= yL - 1 && arr[curY][curX] === 1) {
        arr[curY][curX] = 0;
        queue.push([curX, curY]);
        check[curY][curX] = check[el[1]][el[0]] + 1;
      }
    }
  }
  return -1;
}