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

굥굥이·2022년 5월 10일
0

1. 문제

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

2. 해결 방법

  1. 이 흐름을 확실이 이해하면 될 거 같다. 두 개의 이중 for문으로 모든 좌표를 도는데, 한 좌표씩 돌 때마다 1을 발견하면 DFS를 호출하여 상하좌우대각선을 탐색하고, 그러면 이렇게 하여 생성된 새로운 좌표가 1이라면 또 DFS를 구하여 탐색하는 것이다. 정리하자면 좌표이동 --(1 발견)--> 탐색 --(1 발견)--> 탐색이 될 것이다.
  2. 섬(1)을 발견했다면 0으로 바꿔주어야 하는데, DFS에는 시작좌표도 항상 거쳐가므로 여기에서 board[x][y]=0; 해주는 게 좋을 거 같다.

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];
                function DFS(x, y){
                    board[x][y] = 0;
                    for(let k = 0; k < n; k ++){
                        let nx = x + dx[k];
                        let ny = y + dy[k];
                        if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]===1){
                            DFS(nx, ny);
                        }
                    }
                }
                for(let i = 0; i < n; i ++){
                    for(let j = 0; j < n; j ++){
                        if(board[i][j] === 1){
                            board[i][j] = 0;
                            answer++;
                            DFS(i, j);
                        }
                    }
                }
                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>

4. 반성

제발 x y 실수하지 말자.. 그리고 이거는 체크함수가 필요가 없었다. 조금 헷갈리는군

profile
아자아자 파이띵굥!

0개의 댓글