프로그래머스 게임 맵 최단거리 JavaScript
2023년 1월 18일
문제 풀이
DFS BFS 문제, BFS로 풀었다. 방문했는지 확인하기 위한 배열 check, 방문할 예정인 배열 deque, 이동할 방향 배열 direction 을 선언하고 좌표 1, 1 출발이기에 배열의 인덱스상 0, 0 그리고 블록 수를 deque에 push 한다([0, 0, 1]).
BFS이기에 인덱스 n, m에 처음 만났을 때가 최단 거리이다. 만나면 break한다. 그 외 좌표에서는
maps의 범위 내에서 이동할 좌표의 maps값이 1이고 방문하지 않았으면 duque에 방문할 좌표를 넣어주고 check를 true로 변경한다. 이동할 수 있는 모든 블록을 이동해도 인덱스(n-1, m-1) 을 못 만났으면 -1을 리턴한다.
solution.js
function solution(maps) {
let answer = -1;
const n = maps.length;
const m = maps[0].length;
const check = Array(n).fill().map(() => Array(m).fill(false));
const deque = [[0, 0, 1]];
const direction = [[-1, 0], [0, 1], [1, 0], [0, -1]];
check[0][0] = true;
while (deque.length > 0) {
const [x, y, cnt] = deque.shift();
if (x === n-1 && y === m-1) {
answer = cnt;
break;
}
for (const [dirX, diry] of direction) {
const [dx, dy] = [dirX+x, diry+y];
if (0 <= dx && dx < n && 0 <= dy && dy < m && maps[dx][dy] === 1 && check[dx][dy] === false) {
deque.push([dx, dy, cnt+1]);
check[dx][dy] = true
}
}
}
return answer;
}