9-8) 섬나라 아일랜드(BFS 활용)

16778 단어 BFSBFS

문제

앞의 문제(9-7)와 동일

문제 풀이

코드

9-7과 같은 문제를 BFS를 활용해서 풀이한다. 원리는 다음과 같다.

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <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; //바다로 만듦(check)
                      queue.push([i, j]);
                      answer++; //섬 카운팅(1을 발견하면 섬을 발견한것과 같다!)
                      //queue.length===0이 되면 멈춤
                      while(queue.length){
                        let [x, y]=queue.shift(); //[x, y] 꺼내서, [x, y]와 연결된 좌표 봄(8방향 탐색 통해)
                        console.log(x, y); //test 
                        //[x,y]의 이웃을 찾음(8방향 좌표)
                        for(let k=0; k<8; k++){
                          let nx=x+dx[k];
                          let ny=y+dy[k];
                          if(nx>=0 && nx<n&& ny>=0 && ny<n && board[nx][ny]===1){
                            board[nx][ny]=0;
                            queue.push([nx, ny]);
                          }
                        }
                      }
                      console.log("BFS end")
                    }
                  }
                }
                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>
    </body>
</html>

출력 결과

zap-Logger의 디자인 사고방식
vbs 함수는 그룹 문자열의 마지막 LastOne을 가져오는 데 편리합니다

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage