Toy 문제 25

문제

세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미합니다. 로봇은 지도 위를 일분에 한 칸씩 상하좌우로 이동할 수 있습니다. 로봇의 위치와 목표 지점이 함께 주어질 경우, 로봇이 목표 지점까지 도달하는 데 걸리는 최소 시간을 리턴해야 합니다.

주의사항

• M, N은 20 이하의 자연수입니다.
• src, dst는 항상 로봇이 지나갈 수 있는 통로입니다.
• src에서 dst로 가는 경로가 항상 존재합니다.

입출력 예시

let room = [
  [0, 0, 0, 0, 0, 0],
  [0, 1, 1, 0, 1, 0],
  [0, 1, 0, 0, 0, 0],
  [0, 0, 1, 1, 1, 0],
  [1, 0, 0, 0, 0, 0],
];
let src = [4, 2];
let dst = [2, 2];
let output = robotPath(room, src, dst);
console.log(output); // --> 8

 

수도코드(해석)

목표지점을 향해서 짧은 거리를 이동하는 것이기 때문에 DFS보다는 BFS를 사용하는게 효율적으로 좋습니다.

23번 문제처럼 말판이동을 생각하였지만 DFS의 경우에 가깝기 때문에, 목표 지점까지 도달하는 데 걸리는 최소 시간을 리턴하기에는 좋지 못한 방법입니다.

 

여기서 햇갈렸던 부분은

말판에 step값을 넣어주는 조건문에서 room[row][col] > step 이란 조건 식이 이해가 안갔었는데, 말판에는 당연히 지나가지 않는 부분에는 0또는 1만 있어야 되지 않을까? 라는 생각을 하였는데 곰곰히 생각해보니

코드에 aux 재귀의 문항이 4개가 있는데 이 4개가 동시에 작동이 되어서 그 4개의 뿌리에 뿌리가 작동이 되어서 각각 실행되는 재귀가 영향을 안준다고 생각을 하였습니다.

 

재귀의 하나 하나씩 실행되는 것이 맞다고 생각이 들었습니다. 말판이 벗어나거나, step보다 작은수가 있으면 else로 리턴합니다. 반대로 큰 수가 있을 경우에는 step의 수로 바꾸어 주어서 목표점의 step값을 찾는 것이고, 재귀함수의 탈출은 return문을 작성해주어 동작하지 않게 해준 것입니다.

자세한 내용은 주석을 더 달았습니다.

 

레퍼런스라도 보면 간혹 더 간결하게 깔끔하게 짤 수 있는 부분이 보이지만, 전체적인 그림에서는 확실히 레퍼런스가 좋은것 같습니다.

 

코드(Reference)

const robotPath = function (room, src, dst) {
  
  const aux = (M, N, candi, step) => {
    // 현재 위치
    const [row, col] = candi;

    // 배열의 범위를 벗어난 경우
    if (row < 0 || row >= M || col < 0 || col >= N) return;

    // 말판의 숫자가 0이거나 step보다 말판의 값이 클때 Step으로 바꾸어준다.
    if (room[row][col] === 0 || room[row][col] > step) {
      room[row][col] = step;    
    } else {
      // 장애물이거나 이미 말판에 step보다 작은 수가 있을 경우
      return;
    }
	
    // 각 위치에 대한 재귀 반복
    aux(M, N, [row + 1, col], step + 1); // 상
    aux(M, N, [row - 1, col], step + 1); // 하
    aux(M, N, [row, col - 1], step + 1); // 좌
    aux(M, N, [row, col + 1], step + 1); // 우
  };


  // 시작하는 위치를 다시 돌아 오지 않게하기 위해서
  // 현재 위치에 1를 먼저 카운트 해주고 시작한다.
  aux(room.length, room[0].length, src, 1);

  // 해당 목표지점에 대한 step의 값을 찾기 위한것이고
  // 움직이고 1카운트 한것이 아닌, 1카운트하고 움직였기 때문에 1을 빼준다.
  const [r, c] = dst;
  return room[r][c] - 1;
};