✏️

robotPath

Question

세로와 가로의 길이가 각각 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좌표

Test Case 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
Shell
복사

Test Case 2

Shell
복사

Solve

BFS

const robotPath = function (room, src, dst) {
  const [r, c] = dst;
  const m = room.length;
  const n = room[0].length;

  const bfs = (x, y, count) => {
    if (x < 0 || x >= m || y < 0 || y >= n || room[x][y] < count && room[x][y] !== 0) return;
    room[x][y] = count;

    bfs(x - 1, y, count + 1);
    bfs(x + 1, y, count + 1);
    bfs(x, y - 1, count + 1);
    bfs(x, y + 1, count + 1);
  }
  
  let [srcX, srcY] = src;
  bfs(srcX, srcY, 1);

  return room[r][c] - 1;
};
JavaScript
복사

실행시간 : ms