알고리즘 19 : 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로 가는 경로가 항상 존재합니다.

입출력 예시

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

 

코드

const robotPath = function (room, src, dst) {
  
  const aux = (M,N,tmp,hours)=>{
    const [row,col] = tmp;
    const isValid = (row,col) => row>=0 && col >= 0 && row<M && col<N
    if(isValid(row,col)===false) return ;

    //room[row][col]에 이미 값이 할당되어 있을 경우가 있다.
    //room[row][col]>hours -> 최소 시간을 정해야 하기 때문에 최소값 선택.
    if(room[row][col]===0 || room[row][col]>hours){
    
    //room[row][col]에 할당하는 hours는 몇시간이 걸렸는지를 나타낸다.
    //1시간에 1칸씩 이동하니깐, 이동한 칸수가 곧 시간을 의미한다.
      room[row][col]=hours
    }
    else return ;
    
    //상하좌우로 보낸다.
    //isValid, (room[row][col]===0 || room[row][col]>hours) 조건을 통과하는 방향만 끝까지 간다.
    aux(M,N,[row,col-1],hours+1)
    aux(M,N,[row-1,col],hours+1)
    aux(M,N,[row,col+1],hours+1)
    aux(M,N,[row+1,col],hours+1)
  }
  
  aux(room.length,room[0].length,src,0)
  const [r,c]=dst
  return room[r][c]
};