[JS] 게임 맵 최단거리

BFS의 교과서(?) 적인 문제였던 것 같다.

 

 

dx,dy 배열로 상하좌우 로 갈 방향을 정해주고 visited로 방문했던 곳인지 아닌지를 체크해준다.

 

큐 구조를 활용해서 BFS를 구현하였다. (케이스가 크지않아 실제 큐 구조로 문제를 해결하지는 않았다)

 

ny,nx가 갈 수 있는 범위이면서 방문한 적이 없고 map에서 갈 수 있는 곳이라면 큐에 다음 목적지를 넣어주었다.

 

 

 

 

 

function solution(maps) {
    
    const dx = [1,0,-1,0]
    const dy = [0,1,0,-1]
    
    const m = maps.length
    const n = maps[0].length
    
    
    const visited = [...Array(m)].map(v => Array(n).fill(false))
    
    const que = [[0,0,1]]
    visited[0][0] = true
        
    while (que.length) {
        const [y,x,cnt] = que.shift()
        if (y===(m-1) && x === (n-1)) return cnt
        
        
        for (let k = 0 ; k < 4 ; k ++) {
            const ny = y + dy[k]
            const nx = x + dx[k]
            if (0<= nx && nx < n && 0 <= ny && ny < m && !visited[ny][nx] && maps[ny][nx]){
                que.push([ny,nx,cnt+1])
                visited[ny][nx] = true
            }
        }
    }
    
    return -1
    
}