작성 코드 (1차 시도 / 통과)
function solution(maps) {
let q = [[0, 0]]
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]
while (q.length) {
let [x, y] = q.shift()
for (let i = 0; i < 4; i += 1) {
let nx = x + dx[i]
let ny = y + dy[i]
if (nx < 0 || ny < 0 || nx >= maps.length || ny >= maps[0].length) continue
if (maps[nx][ny] === 0 || nx === 0 && ny === 0) continue
if (maps[nx][ny] === 1) {
maps[nx][ny] = maps[x][y] + 1
q.push([nx, ny])
}
}
}
return maps[maps.length - 1][maps[0].length - 1] === 1 ? -1 : maps[maps.length - 1][maps[0].length - 1]
}
구현 로직
최단 거리 관련은 BFS 문제일 확률이 높습니다. BFS는 큐 사용이 일반적인데 자바스크립트로는 shift와 push로 간단하게 사용할 수 있습니다. 문제에서 최대 10000개의 데이터가 들어갈 수 있으니 성능상 큰 문제는 없습니다.
주변칸 탐색을 위한 인덱스 배열 dx dy를 만들어두고 큐에 시작점을 넣어줍니다. 큐에서 원소하나를 빼서 해당 칸의 상하좌우를 확인하여 이동가능한 경우 이전칸 + 1값을 매겨주면 출발지부터 해당칸까지의 거리가 계산됩니다.
케이스1의 경우 다음과 같이 maps가 구성됩니다.
[
[ 1, 0, 9, 10, 11 ],
[ 2, 0, 8, 0, 10 ],
[ 3, 0, 7, 8, 9 ],
[ 4, 5, 6, 0, 10 ],
[ 0, 0, 0, 0, 11 ]
]
따라서 마지막 칸에는 출발지부터의 최단 거리가 입력됩니다. 도달할 수 없는 경우 도착점은 여전히 1의 값을 가지게 될것이므로 해당 경우를 고려하여 결과를 리턴해주면 됩니다.