robotPath 2
Problem
세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미한다. 로봇은 한 번에 임의의 k칸 직진과 90도 회전 중 1가지 동작을 할 수 있다. 로봇의 현재 위치와 방향, 목표 지점과 방향이 함께 주어진다. 이 때, 방향은 위쪽이 1, 오른쪽이 2, 아래쪽이 3, 왼쪽이 4로 주어진다. 로봇이 목표 지점까지 도달해 목표 방향으로 회전하는 데 필요한 동작의 수를 리턴해야 한다.
입력
인자 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 : sDir
- number 타입의 자연수
인자 4 : dst
- number 타입을 요소로 갖는 배열
- dst.length는 2
- dst[i]는 0 이상의 정수
- dst의 요소는 차례대로 좌표평면 위의 y좌표, x좌표
인자 5 : dDir
- number 타입의 자연수
출력
number 타입을 리턴
주의사항
M, N은 20 이하의 자연수.
src, dst는 항상 로봇이 지나갈 수 있는 통로이다.
src에서 dst로 가는 경로가 항상 존재한다.
목표 지점에 도달한 후 방향까지 일치해야 한다.
직진은 1칸 직진이 아니라 임의의 k칸을 직진할 수 있다. 즉 한번의 직진 명령으로 장애물이 없는 한 계속 갈 수 있다.
왼쪽에서 오른쪽 또는 아래에서 위쪽으로 방향을 바꾸는 데 총 2번의 회전 동작이 필요하다.
입출력 예시
let room = [
[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 1, 0, 0],
[0, 0, 1, 1],
];
let src = [3, 0];
let sDir = 3;
let dst = [2, 2];
let dDir = 2;
let output = robotPath2(room, src, sDir, dst, dDir);
console.log(output); // --> 11
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],
];
src = [4, 2];
sDir = 1;
dst = [2, 2];
dDir = 3;
output = robotPath2(room, src, sDir, dst, dDir);
console.log(output); // --> 7
Solution
queue를 이용한 BFS로 탐색하나 직진 시 1칸 직진이 아니라 임의의 k칸을 직진할 수 있도록 한다.
// file:'RobotPath2.js'
const robotPath2 = function (room, src, sDir, dst, dDir) {
// n은 가로(x) m은 세로(y) 이다.
const n = room[0].length;
const m = room.length;
// 이동할 네 가지 방향을 정의한다. (위쪽(1), 오른쪽(2), 아래쪽(3), 왼쪽(4) 순)
const dx = [0, 0, 1, 0, -1];
const dy = [0, -1, 0, 1, 0];
let result = 0;
// room을 직접 바꾸어 답을 도출할 것이므로 오류를 막기위해 장애물인 1을 -1로 바꾸어 준다.
room = room.map(el => el.map(el => el==1?-1:el));
// BFS를 구현할 큐를 만들고 시작 노드의 좌표와 방향을 넣는다.
const queue = [];
queue.push([src[0], src[1], sDir]);
// BFS를 수행한다. (큐가 바닥날 때까지 수행하면 된다.)
while (queue.length) {
// 반복할 떄 마다 큐에서 원소를 꺼내고,
const [y,x,dir] = queue.shift()
// 현재 위치에서 4가지 방향으로 한번씩 방문한다.
for (let i = 1; i < 5; i++) {
let k = 0;
// i방향으로 임의의 k칸을 쭉 직진하며 같은 값을 넣어준다.
while (true) {
k += 1;
let ny = y + k * dy[i];
let nx = x + k * dx[i];
// 공간을 벗어난 경우 이 반복을 탈출한다.
if (nx < 0 || nx >= n || ny < 0 || ny >= m) break;
// 방문한 적이 있거나 장애물을 만났거나 목적지에 도착했을 시 이 반복을 탈출한다.
if (room[ny][nx] !== 0 || (ny === src[0] && nx === src[1])) break;
// 위의 경우가 아니라면 방문한 노드에 직진 시작 노드값 + 방향전환 동작수 + 직진동작수(1)를 할당한다.
room[ny][nx] = room[y][x] + (Math.abs(dir-i)===3 ? 1 : Math.abs(dir-i)) + 1;
// 방문 노드의 좌표와 방향을 큐에 넣는다.
queue.push([ny, nx, i]);
}
}
// 목적지에 도달했다면 도착지 방향전환(dDir)을 수행하고(그 동작만큼 목적지 노드 값에 더해준다) 탐색을 멈춘다.
if (y === dst[0] && x === dst[1]) {
result = room[y][x] + (Math.abs(dir-dDir)===3 ? 1 : Math.abs(dir-dDir))
break;
}
}
return result;
};