[JS] 무인도 여행

BFS를 활용해서 문제를 풀어보았다.

 

배열을 순회하면서 숫자가 적힌 지점부터 BFS를 적용하여 수들을 더해 나갔다. 이때, 방문했던 곳이라면 다시 방문할 필요가 없기 때문에 방문했는지 여부를 저장할 배열을 하나 두었다.

 

2차원 배열을 한번 순회한 이후, 정렬을 해주었고 섬이 없다면 [-1]을 반환하게 설정해주며 마무리하였다.

 

 

function solution(maps) {
    
    const dx = [1,0,-1,0]
    const dy = [0,1,0,-1]
    
    const dp = [...new Array(maps.length)].map((_,i) => [...new Array(maps[0].length)].fill(0))
    
    ret = []
    
    for (let i = 0 ; i< maps.length ; i++) {
        for ( let j = 0 ; j < maps[0].length ; j++){
            if (maps[i][j] !== 'X' && !dp[i][j]){
                let cnt = 0
                const que = [[j,i]]
                while (que.length) {
                    const [x,y] = que.shift()
                    if (dp[y][x]) continue
                    
                    cnt += +maps[y][x]
                    dp[y][x] = 1
                    for ( let k =0;k<4;k++ ){
                        const [nx,ny] = [x+dx[k],y+dy[k]]
                        if (0<=nx && nx<maps[0].length && 0<= ny && ny < maps.length && !dp[ny][nx] && maps[ny][nx] !== 'X') {  
                            que.push([nx,ny])
                        }
                    }
                }
                ret.push(cnt)
            }
        }
    }
    
    
    ret.sort((a,b) => a-b)
    
    return ret.length ? ret : [-1]
}