PS/Programmers
Programmers / Level 2 / 게임 맵 최단거리 / JS
KimMinJun
2022. 12. 10. 22:17
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
function solution(maps) {
const MAPS_ROW = maps.length - 1;
const MAPS_COL = maps[0].length - 1;
const isValid = (row, col) => {
if(row < 0 || row > MAPS_ROW) return false;
if(col < 0 || col > MAPS_COL) return false;
if(maps[row][col] === 0) return false;
return true;
}
const DIR = {
UP: [-1, 0],
DOWN: [1, 0],
LEFT: [0, -1],
RIGHT: [0, 1],
};
const BFS = () => {
// [row, col, distance]
let queue = [[0, 0, 1]];
while(queue.length) {
let [row, col, distance] = queue.shift();
// 끝에 다다랐다면 거리 return
if(row === MAPS_ROW && col === MAPS_COL) return distance;
for(const [DIR_ROW, DIR_COL] of Object.values(DIR)) {
const [NEXT_ROW, NEXT_COL] = [row + DIR_ROW, col + DIR_COL];
if(isValid(NEXT_ROW, NEXT_COL) === false) continue;
// 지나온 길은 0으로 바꿔줌
maps[NEXT_ROW][NEXT_COL] = 0;
queue.push([NEXT_ROW, NEXT_COL, distance + 1]);
}
}
return -1;
}
return BFS();
}