2024.11.15 BFS

문제: BFS 지도 탐색

문제설명

• 2차원 배열 형태로 주어진 지도에서 숫자로 표시된 영역의 합을 구하는 문제
• X는 벽으로 간주하며 탐색할 수 없음
• 연결된 숫자 영역의 합을 계산하여 오름차순으로 정렬된 결과를 반환
• 연결된 영역이 없으면 [-1]을 반환

문제접근방법

1. 그래프 탐색
2. BFS or DFS
3. 방문 기록

코드

function solution(maps) {
    const visited = Array.from({length: maps.length}, () => Array(maps[0].length).fill(false));
    const direction = [[1,0], [-1,0], [0,1], [0,-1]];
    
    const bfs = (startX, startY) => {
        let queue = [[startX, startY]];
        let sum = 0;
        
        while(queue.length > 0){
            const [x, y] = queue.shift();
            if(visited[x][y]) continue;
            
            visited[x][y] = true;
            
            sum += Number(maps[x][y]);
            
            for(let [dx, dy] of direction){
                const nextX = x + dx;
                const nextY = y + dy;
                
                if(nextX >= 0 && nextX < maps.length && nextY >= 0 && nextY < maps[0].length){
                    if(maps[nextX][nextY] !== 'X' && !visited[nextX][nextY]){
                        queue.push([nextX, nextY])
                    }
                }
            }
        }
        return sum;
    }
    
    const result = [];
    for(let i = 0; i < maps.length; i++){
        for(let j = 0; j < maps[i].length; j++){
            if(maps[i][j] !== 'X' && !visited[i][j]){
                result.push(bfs(i,j));
            }
        }
    }
    
    return result.length > 0 ? result.sort((a, b) => a - b) : [-1];
}