2022/05/09) 7. 섬나라 아일랜드(BFS) [그래프와 탐색(DFS, BFS(넓이우선))]

1. 문제

<섬나라 아일랜드>
: N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다다. 몇 개의 섬이 있는지 구하는 프로그램을 작성한다.

2. 해결 방법

1. 앞에서 DFS에서 했던 흐름과 같다.

• DFS : 좌표를 구한 후, 섬(1)이면 값(x,y)을 넘겨 재귀함수(DFS) 호출해서 탐색. 그리고 또 섬(1)을 발견하면 재귀함수(DFS) 호출
• BFS : 좌표를 구한 후, 섬(1)이면 queue에 push하고 while문에서 shift()해서 탐색. 그리고 또 섬(1)을 발견하면 queue에 push하고 while문에서 shift().
• DFS에서의 출발점은 재귀함수에 넘기는 값이고, BFS에서의 출발점은 push한 값이다.

2. queue 흐름을 그림으로 보도록 하자. 상하좌우비대칭 탐색 후 섬이 없으면, push를 할 게 없으므로, queue에 있던 것들이 다 shift돼서 나간다. 그러면 while문의 조건에 적합하지 않으므로 while문은 끝나고, 다시 for문 흐름대로 간다. 다시 좌표를 찾으러!
   위의 그림처럼 [ , ] 형태로 넘겨야 하는 걸 잊지 말자.. 이거 때문에 자꾸 실수가 발생..

3. 정답

        <script>
            function solution(board){  
                let answer=0;
                let n=board.length;
                let dx=[-1, -1, 0, 1, 1, 1, 0, -1];
                let dy=[0, 1, 1, 1, 0, -1, -1, -1];
                let queue=[];
                for(let i=0; i<n; i++){
                    for(let j=0; j<n; j++){
                        if(board[i][j]===1){
                            board[i][j]=0; //체크!!!
                            queue.push([i, j]); //board[i][j]가 아니라, [i,j]를 보내주면 된다.
                            answer++;
                            while(queue.length){
                                let x=queue.shift(); //그러면 x에 [[,],[,]]형태로 들어감
                                for(let k=0; k<8; k++){
                                    let nx=x[0]+dx[k]; //인덱스번호로 추출
                                    let ny=x[1]+dy[k];
                                    if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]===1){
                                        board[nx][ny]=0; //체크!!!
                                        queue.push([nx, ny]);
                                    }
                                }
                            }
                        }
                    }
                }
                return answer;
            }
            let arr=[[1, 1, 0, 0, 0, 1, 0], 
                     [0, 1, 1, 0, 1, 1, 0],
                     [0, 1, 0, 0, 0, 0, 0],
                     [0, 0, 0, 1, 0, 1, 1],
                     [1, 1, 0, 1, 1, 0, 0],
                     [1, 0, 0, 0, 1, 0, 0],
                     [1, 0, 1, 0, 1, 0, 0]];
            console.log(solution(arr));
        </script>