robotPath

문제

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

입력

• 인자 1 : room
  • 배열을 요소로 갖는 배열
  • room.length는 M
  • room[i]는 number 타입을 요소로 갖는 배열
  • room[i].length는 N
  • room[i][j]는 세로로 i, 가로로 j인 지점의 정보를 의미
  • room[i][j]는 0 또는 1
    
• 인자 2 : src
  • number 타입을 요소로 갖는 배열
  • src.length는 2
  • src[i]는 0 이상의 정수
  • src의 요소는 차례대로 좌표평면 위의 y좌표, x좌표
• 인자 3 : dst
  • number 타입을 요소로 갖는 배열
  • dst.length는 2
  • dst[i]는 0 이상의 정수
  • dst의 요소는 차례대로 좌표평면 위의 y좌표, x좌표
    출력
  • number 타입을 리턴해야 합니다.
• 주의사항
  • M, N은 20 이하의 자연수입니다.
  • src, dst는 항상 로봇이 지나갈 수 있는 통로입니다.
  • src에서 dst로 가는 경로가 항상 존재합니다.

레퍼런스 코드

const robotPath = function (room, src, dst) {
  const aux = (M, N, candi, time) => {
    const [row, col] = candi;
    if(row<0 || col<0 || row>=M || col>=N) return;
    if(room[row][col] ===0 || room[row][col]>time) {
      room[row][col] = time;
    } else {
      return;
    }
    
    aux(M, N, [row+1, col], time+1); 
    aux(M, N, [row-1, col], time+1);
    aux(M, N, [row, col-1], time+1);
    aux(M, N, [row, col+1], time+1);
  };
  
  aux(room.length, room[0].length, src, 1);
  //시작지점까지 걸린 시간은 0분이지만 방문했음을 표시하기 위해 1로 시작한다.
  
  const [r, c] = dst;
  return room[r][c]-1; //1분부터 시작했으므로 다시 1을 빼준다.
}

디버깅

실행순서가 이해되지 않아서 다음과 같이 값을 설정하고 디버깅 해보았다.

let room = [
  [0, 1],
  [0, 0],
];
let src = [0,0];
let dst = [1,1];
robotPath(room, src, dst);

다음은 18번째에서 호출한 aux가 첫번째 자식 노드를 끝까지 탐색하는 과정을 작성해보았다.

• 첫번째 aux(room.length, room[0].length, src, 1) 실행
  • 콜스택에는 하나의 aux가 담겨있고, 6번째줄 조건문에 걸려서 room[0][0]=1이 저장된다.
  • 조건문을 빠져나오면 12번째에서 또다시 두번째 aux를 호출한다. (아직 18번째에서 호출한 aux는 끝나지 않은 상태)
  • 또다시 12번째에서 세번째 aux를 호출한다. (지금까지 첫번째, 두번째 aux는 끝나지 않은 상태)
    • 그런데, row가 배열의 범위를 넘어갔으므로 리턴되었다.
  • 세번째 aux가 리턴되었으므로 두번째 aux가 13번째에서 네번쨰 aux를 호출한다. (두번째 aux로 돌아왔고 네번째 aux가 호출됨)
    • 네번째 aux는 조건을 만족하지 않아 리턴된다.
  • 두번째 aux가 14번째줄에서 다섯번째 aux를 호출한다.
    • 다섯번째 aux는 조건을 만족하지 않아 리턴된다.
  • 두번째 aux가 15번째줄에서 여섯번째 aux를 호출한다.
    • 여섯번째 aux는 room[row][col]===1로 장애물이므로 리턴된다.
  • 드디어 두번째 aux가 끝났다.
• 다시 첫번째 aux로 돌아와서 첫번째 aux가 13번째줄에서 aux를 호출한다.

배열의 모든 경로를 DFS 탐색한 후에 도착지점에 저장된 시간을 리턴한다. 풀이의 구조를 보면, 함수 aux를 작성하고, 함수 내부에서 함수를 반복호출한다. 이때 각각은 상,하,좌,우로 이동하는 것이다.
함수를 정의한 후에 함수를 호출한다. 호출된 함수의 모든 실행이 끝나면, 배열 room의 dst값을 조회하여 걸린 시간을 리턴한다.

디버깅없이 풀이만으로는 이해하기가 어려웠는데 디버깅을 하면서 보니까 가장 마지막 depth까지 확인하고 한 depth위로 돌아와 해당 노드의 마지막 depth까지 다시 확인하고, 이 과정을 반복하는 것을 알 수 있었다.