[프로그래머스] 게임 맵 최단거리 풀이 / JavaScript

프로그래머스

 

작성 코드 (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의 값을 가지게 될것이므로 해당 경우를 고려하여 결과를 리턴해주면 됩니다.