<섬나라 아일랜드>
: N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다다. 몇 개의 섬이 있는지 구하는 프로그램을 작성한다.
- 이 흐름을 확실이 이해하면 될 거 같다. 두 개의 이중 for문으로 모든 좌표를 도는데, 한 좌표씩 돌 때마다 1을 발견하면 DFS를 호출하여 상하좌우대각선을 탐색하고, 그러면 이렇게 하여 생성된 새로운 좌표가 1이라면 또 DFS를 구하여 탐색하는 것이다. 정리하자면
좌표이동 --(1 발견)--> 탐색 --(1 발견)--> 탐색
이 될 것이다.- 섬(1)을 발견했다면 0으로 바꿔주어야 하는데, DFS에는 시작좌표도 항상 거쳐가므로 여기에서 board[x][y]=0; 해주는 게 좋을 거 같다.
<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>
제발 x y 실수하지 말자.. 그리고 이거는 체크함수가 필요가 없었다. 조금 헷갈리는군