문제
세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미합니다. 로봇은 한 번에 임의의 k칸 직진과 90도 회전 중 1가지 동작을 할 수 있다. 로봇의 현재 위치와 방향, 목표 지점과 방향이 함께 주어집니다. 이 때, 방향은 위쪽이 1, 오른쪽이 2, 아래쪽이 3, 왼쪽이 4로 주어집니다. 로봇이 목표 지점까지 도달해 목표 방향으로 회전하는 데 필요한 동작의 수를 리턴해야 합니다.
입력
인자 1 : room
- 배열을 요소로 갖는 배열
room.length는 Mroom[i]는number타입을 요소로 갖는 배열room[i].length는 Nroom[i][j]는 세로로 i, 가로로 j인 지점의 정보를 의미room[i][j]는 0 또는 1
인자 2 : src
number타입을 요소로 갖는 배열src.length는 2src[i]는 0 이상의 정수src의 요소는 차례대로 좌표평면 위의 y좌표, x좌표
인자 3 : sDir
number타입의 자연수
인자 4 : dst
number타입을 요소로 갖는 배열dst.length는 2dst[i]는 0 이상의 정수dst의 요소는 차례대로 좌표평면 위의 y좌표, x좌표
인자 3 : 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
/*
1. 시작 - (3, 0)에서 아래 방향을 향한 상태
장애물은 x로 표시, 출발지점은 s로 표시
[
[0, 0, 0, 0],
[0, x, x, 0],
[0, x, 0, 0],
[s, 0, x, x],
]
2. 로봇은 아래 방향을 향하고 있음
3인 이유: 위로 가기 위해서는 90도 회전이 2번, 직진 1번 필요함. 직진 한번으로 도달할 수 있는 모든 칸을 표기.
2인 이유: 오른쪽으로 가기 위해서는 90도 회전 1번, 직진 1번이 필요함
[
[3, 0, 0, 0],
[3, x, x, 0],
[3, x, 0, 0],
[s, 2, x, x],
]
3. (0, 0) 지점에서 로봇은 위 방향을 향하고 있음
5인 이유: 오른쪽으로 가기 위해서는 90도 회전이 1번, 직진 1번 필요함.
1인 이유: 직진 1번으로 충분
[
[3, 5, 5, 5],
[3, x, x, 0],
[3, x, 0, 0],
[s, 2, x, x],
]
4. 비슷한 방식으로 계산하면 최종적으로 방향 전환까지 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- MOVES변수에 방향과 상하좌우 좌표를 배열에 담아 놓는다.
- 출발점에서 시작해서 처음으로 이동할 4가지의 방향을 탐색을 시작한다.
- 재귀함수에서 다음 좌표로 이동가능한지, 몸을 몇번 틀어야 하는지를 계산한다.
- 몸의 방향이 같고, 이동방향이 같다면 한번에 이동이 가능하기 때문에 count는 계산하지 않는다.
- 그외 방향이 다른경우는 계산한 count를 더해주고 다음 상하좌우로 이동하며 걸어온 시간들을 좌표에 찍는다.
- 목적지의 시간을 리턴한다.
Solution
const robotPath2 = function (room, src, sDir, dst, dDir) {
let R = room.length;
let C = room[0].length;
const MOVES = [
[1, -1, 0],
[2, 0, 1],
[3, 1, 0],
[4, 0, -1],
];
for (let i = 0; i < R; i++) {
for (let j = 0; j < C; j++) {
if (src[0] === i && src[1] === j) {
room[i][j] = 's'
} else if (room[i][j] === 1) {
room[i][j] = 'x'
}
}
}
const isValid = (row, col) => {
if (row >= 0 && row < R && col >= 0 && col < C && room[row][col] !== 'x' && room[row][col] !== 's') {
return true
} else {
return false
}
}
const rotate = (curD, nextD) => {
let rot = 0
rot = Math.abs(curD - nextD)
if (rot > 2) {
rot = 1
}
return rot
}
const aux = (loc, dir, count, ndir) => {
const [nextDir, nextR, nextC] = ndir;
let r = loc[0] + nextR
let c = loc[1] + nextC
let rot = 0
if (isValid(r, c)) {
if (dir !== nextDir) {
count++
rot = rotate(dir, nextDir)
}
} else {
return
}
if (count === 0 && dir === nextDir) {
// 현재 방향과, 나갈 방향이 같고, 첫걸음이라면 1을 더해줘야 한다.
count++
}
count += rot
if (room[r][c] !== 0) {
if (room[r][c] > count) {
room[r][c] = count
} else {
return
}
} else {
room[r][c] = count
}
if (r === dst[0] && c === dst[1]) {
let result = rotate(nextDir, dDir)
count += result
room[r][c] = count
}
aux([r, c], nextDir, count, MOVES[0]);
aux([r, c], nextDir, count, MOVES[1]);
aux([r, c], nextDir, count, MOVES[2]);
aux([r, c], nextDir, count, MOVES[3]);
};
aux(src, sDir, 0, MOVES[0]);
aux(src, sDir, 0, MOVES[1]);
aux(src, sDir, 0, MOVES[2]);
aux(src, sDir, 0, MOVES[3]);
const [r, c] = dst;
return room[r][c]
};
/*
스택, 큐 보다는 재귀를 자주 쓰게 되는 것 같다.
중간에 논리가 조금 부족해 테스트를 전부 통과하지 못했지만 결국 해결했다.
*/
안녕하세요.