LeetCode - Number of Islands (Javascript)

Description

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ['1', '1', '1', '1', '0'],
  ['1', '1', '0', '1', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '0', '0', '0'],
];
Output: 1;

Example 2:

Input: grid = [
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1'],
];
Output: 3;

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'

---

소스코드

function numIslands(grid) {
  let answer = 0;
  const maxRow = grid.length - 1;
  const maxColumn = grid[0].length - 1;

  function traverse(row, col, grid) {
    // 재귀 endPoint
    if (
      grid[row] === undefined ||
      grid[row][col] === undefined ||
      grid[row][col] === '0'
    ) {
      return;
    }
    // 위 조건 통과하면 현재 탐색하고 있는 node가 1이라는 뜻 => 0으로 바꿔줌
    grid[row][col] = '0';
    // 재귀 시작 (상하좌우 탐색)
    traverse(row - 1, col, grid);
    traverse(row, col + 1, grid);
    traverse(row + 1, col, grid);
    traverse(row, col - 1, grid);
  }

  for (let i = 0; i <= maxRow; i++) {
    for (let j = 0; j <= maxColumn; j++) {
      if (grid[i][j] === '1') {
        // 완전 탐색을 하는 것이기 때문에, 처음 1이 발견됐을 때 하나의 섬이 모두 0으로 바뀔 것이다.
        // 하지만 만약 다음 탐색에서 어떤 node가 1이라면, 그건 다른 동떨어져있는 섬일 것이다. (이전 섬은 모두 0이 된 상태기 때문)
        answer++;
        // 그러면 그 node를 다시 탐색하며 모두 0으로 바꿔주는 작업을 반복한다.
        traverse(i, j, grid);
      }
    }
  }
  return answer;
}

---