리코쳇 로봇이라는 보드게임이 있습니다.
이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.
이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.
다음은 보드게임판을 나타낸 예시입니다.
...D..R
.D.G...
....D.D
D....D.
..D....
여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.
게임판의 상태를 나타내는 문자열 배열 board
가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.
board
의 길이 ≤ 100
board
의 원소의 길이 ≤ 100board
의 원소의 길이는 모두 동일합니다.board | result |
---|---|
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."] | 7 |
[".D.R", "....", ".G..", "...D"] | -1 |
입출력 예 #1
입출력 예 #2
.D.R
....
.G..
...D
⭐️ 방향의 도착지가 G여야 한다.
function solution(board) {
var answer = 0;
board = board.map(items => items.split(''));
const q = [];
const n =board.length; // 가로 길이
const m = board[0].length; // 세로 길이
const dx = [-1, 1, 0, 0]; // 상하좌우 방향
const dy = [0, 0, -1, 1];
board.forEach((items, i) => {
items.forEach((item, j) => {
if(item === 'R') q.push([i, j]); // 시작 위치
});
});
// 1) 시작 위치를 다시 방문하지 않게 'O' 표시
board[q[0][0]][q[0][1]] = 'O';
// 2) q의 길이 만큼 반복
while(q.length) {
// 3) 횟수(answer)를 카운트하기 위해 현재 q의 길이를 고정시킨다.
const size = q.length;
// 4) 고정시킨 길이만큼 반복한다.
for(let i=0; i<size; i++) {
const [x, y] = q.shift();
// 5) 상하좌우 한번씩 확인
for(let j=0; j<4; j++) {
// 6) 다음 이동 위치
let nx = x + dx[j];
let ny = y + dy[j];
// 7) 게임판 범위와 벽(D)를 만나지 않을 경우만 미끄러진다.
while(nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] !== 'D') {
nx += dx[j];
ny += dy[j];
}
// 8) 현재 위치로 변경한다.
nx -= dx[j];
ny -= dy[j];
// 9) 현재 위치가 도착(G) 지점이면 횟수(answer)를 1증가 후 반환한다.
if(board[nx][ny] === 'G') return answer+1;
// 10) 한번이라도 방문한적이 없을 경우만
if(board[nx][ny] !== 'O') {
// 11) 방문 표시(O) 후 q에 담는다.
board[nx][ny] = 'O';
q.push([nx, ny]);
}
}
}
answer++;
}
return -1;
}