[알고리즘] LeetCode Number of IsLands

1. 개요

섬의 갯수를 구하는 전형적인 DFS 문제이다

 

2차원 배열로 섬이 주어질 때 전체 섬이 몇개있는지 구하는 문제였다

Number of Islands - LeetCode

 

 

 

 

2. 풀이

우선 배열 전체를 탐색하면서 문자 "1"을 찾아야했다.

만약 1을 발견했다면 해당 지점부터 DFS탐색을하며 1을 전부 0으로 바꿔준 후 섬의 갯수를 하나 증가시켜준다

이때 주의해야할 점은 대각선으로 1이 대각선으로 붙어있다면 서로 떨어져있는 것으로 본다는 것이다.

 

매번 DFS를 푸는 방식을 통해 해결했다. 거의 대부분의 DFS는 이렇게 구현하는 거라고 그냥 암기하는게 편할거같다.

/**
 * @param {character[][]} grid
 * @return {number}
 *
 * 섬 갯수찾기
 */
var numIslands = function (grid) {
  let answer = 0;
  const m = grid.length;
  const n = grid[0].length;
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  // 대각은 포함되면 안된다..

  function DFS(cx, cy) {
    for (let i = 0; i < dx.length; i++) {
      const nx = cx + dx[i];
      const ny = cy + dy[i];
      if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === "1") {
        grid[nx][ny] = "0";
        DFS(nx, ny);
      }
    }
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        grid[i][j] = 0;
        DFS(i, j);
        answer += 1;
      }
    }
  }

  return answer;
};JAVASCRIPT