[알고리즘] LeetCode Number of IsLands

개요

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

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

Number of Islands - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com

풀이

우선 배열 전체를 탐색하면서 문자 “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;
};