<섬나라 아일랜드>
: N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다다. 몇 개의 섬이 있는지 구하는 프로그램을 작성한다.
- 앞에서 DFS에서 했던 흐름과 같다.
DFS
: 좌표를 구한 후, 섬(1)이면 값(x,y)을 넘겨 재귀함수(DFS) 호출해서 탐색. 그리고 또 섬(1)을 발견하면 재귀함수(DFS) 호출BFS
: 좌표를 구한 후, 섬(1)이면 queue에 push하고 while문에서 shift()해서 탐색. 그리고 또 섬(1)을 발견하면 queue에 push하고 while문에서 shift().DFS에서의 출발점
은 재귀함수에 넘기는 값이고,BFS에서의 출발점
은 push한 값이다.
- queue 흐름을 그림으로 보도록 하자. 상하좌우비대칭 탐색 후 섬이 없으면, push를 할 게 없으므로, queue에 있던 것들이 다 shift돼서 나간다. 그러면 while문의 조건에 적합하지 않으므로 while문은 끝나고, 다시 for문 흐름대로 간다. 다시 좌표를 찾으러!
위의 그림처럼 [ , ] 형태로 넘겨야 하는 걸 잊지 말자.. 이거 때문에 자꾸 실수가 발생..
<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>