[프로그래머스#JS] 게임 맵 최단거리
문제
게임 맵 최단거리 https://programmers.co.kr/learn/courses/30/lessons/1844
해결
목적지까지 최단거리를 구하는 문제이기 때문에 BFS를 이용하여 구현했습니다.
남서북동 순으로 dy, dx를 구현한 후, 0 ~ 4 까지의 index를 이용하여 이동할 수 있는지 체크 후, 이전 칸 +1을 하면서 현재 위치의 최단 거리를 계산합니다.
초기 세팅을 1로 했는데 목적지의 count가 1이라면 도달할 수 없다는 뜻 입니다.
코드
function solution(maps) {
// 남서북동 순서
const dy = [1, 0, -1, 0];
const dx = [0, -1, 0, 1];
const row = maps.length; // 행
const col = maps[0].length; // 열
const visitCount = [...maps].map((r) => r.map((c) => 1));
let temp = 0;
const queue = [[0, 0]];
while (queue.length) {
const [y, x] = queue.shift();
for (let k = 0; k < 4; k++) {
const ny = y + dy[k];
const nx = x + dx[k];
if (ny >= 0 && nx >= 0 && ny < row && nx < col) {
if (maps[ny][nx] === 1 && visitCount[ny][nx] === 1) {
visitCount[ny][nx] = visitCount[y][x] + 1;
queue.push([ny, nx]);
}
}
}
}
return visitCount[row - 1][col - 1] === 1 ? -1 : visitCount[row - 1][col - 1];
}
Author And Source
이 문제에 관하여([프로그래머스#JS] 게임 맵 최단거리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tunakim/프로그래머스JS-게임-맵-최단거리-88gf7y8f저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)