JavaScript Algorithm - robotPath

 

 

문제설명 : 

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

입력

인자 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) {
    // TODO: 여기에 코드를 작성합니다.


    const aux = (M, N, candi, step)=>{
        //현재 위치
        const [row, col] = candi 

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

        //현재위치가 0 이거나 현재위치가 step보다 클 때 
        if(room[row][col] === 0 || room[row][col] > step){
            //현재 위치에 step값을 대입 
            room[row][col] = step; 
        }
        else{
            //장애물(1)이거나 이미 최소시간(1)으로 통과한 경우
            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) //우

    };
    //M이 행
    //N이 열 
    // 로봇이 있는 위치를 1로 초기화하면 바로 옆 통로는 2가 된다.
    // 계산이 완료된 후에 최종값에 1을 빼줘야한다.
    aux(room.length, room[0].length, src, 1)

    const [r, c] = dst;
    return room[r][c] -1 
  };
  
  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

 

풀이 코드2

풀이 코드1 보다 조금 더 간결한 코드입니다.

  const robotPath2 = function (room, src, dst) {
    const M = room.length;
    const N = room[0].length;

    const aux = (candi, step) => {
        const [row, col] = candi;
        if (row < 0 || row >= M || col < 0 || col >= N) {
            return;
        }

        if (room[row][col] === 0 || room[row][col] > step) {
            room[row][col] = step;
        } else {
            return;
        }

        aux([row + 1, col], step + 1);
        aux([row - 1, col], step + 1);
        aux([row, col - 1], step + 1);
        aux([row, col + 1], step + 1);
    };

    aux(src, 1);

    const [r, c] = dst;
    return room[r][c] - 1;
};
  
  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