1. 섬나라 아일랜드

map이라는 array가 주어지고 1로 이루어진 섬이 몇개 있는지 체크하면 된다.

2. 접근 방법

먼저 간단하게 생각해보자. 일단 지도를 다 둘러봐야하므로 이중포문이 필요할 것이고 이중 포문안에서 돌다가 1을 찾으면 닻을내리고 그 섬안을 또다시 다 둘러봐야하므로 재귀나 또 다른 포문이 필요할 것이다.

우선 좌표를 또 설정한다. 이번에는 미로찾기에서 처럼 4방향으로 설정하는게 아니라, 대각선 까지 포함해서 봐야하기 때문에 8방향을 설정한다. X,Y축에서 위, 아래, 옆, 대각선으로 가기 위한 방법을 잘 생각해보자.

• pseudo code
  • 미로찾기와 마찬가지로 next x , next y를 설정한다.
  • map의 모든 x,y의 좌표를 돌면서 확인해야한다. 그래서 x,y를 pass해주기 위해서 이중 포문을 만들고 그 안에 dfs를 실행하고 dfs안에 좌표를 pass한다.
  • dfs안에서는 다음 좌표를 설정하고 이동가능한지 여부를 살펴본다.
  • 이동가능하면 이동한곳을 0으로 만들고(바다로 만들고) dfs에 다음 좌표를 넣는다.

function island(map) {
  let found = false;
  let dx = [-1, 0, 1, 0, 1, -1, -1, 1];
  let dy = [0, 1, 0, -1, 1, -1, 1, -1];
  let answer = 0;

  function dfs(x, y) {
    for (let i = 0; i < dx.length; i++) {
      let nx = x + dx[j];
      let ny = y + dy[j];
      if (
        nx >= 0 &&
        nx < map.length &&
        ny >= 0 &&
        ny < map.length &&
        map[nx][ny] === 1
      ) {
        map[nx][ny] = 0;
        dfs(nx, ny);
      }
    }
  }

  for (let i = 0; i < map.length; i++) {
    for (let j = 0; j < map.length; j++) {
      if (map[i][j] === 1) {
        ++answer;
        dfs(i, j);
      }
    }
  }

  return answer;
  // 5
}

let map = [
  [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],
];

끝! 미로찾기와 다르게 지나간자리를 다시 되돌리지 않는다. 되돌리면 찾은섬을 또 찾는게 되어버리니깐 말이다.