200. Number of Islands

200. Number of Islands

문제

테스트 케이스

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

풀이

변수 'islandCounts'로 섬의 갯수를 카운팅한다.

1. 반복문으로 셀을 방문하면서 1(육지) 또는 0(바다)인지 확인한다.
2. 육지를 발견했으니 islandCounts를 하나 증가시킨다.
3. 발견한 육지(일부)를 시작으로 dfs를 반복해 상하좌우로 인접한 육지가 있는지 확인한다.
4. 이 때 현재 접근한 육지를 다시 방문하지 않도록 "0"으로 초기화한다.
5. (반복) 재귀적으로 dfs 함수를 호출한다.
6. 모든 셀을 방문하면 islandCounts를 반환한다.

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  let islandCounts = 0;

  var dfs = function(r, c) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] === '0') {
      return 0
    }

    grid[r][c] = "0";
    dfs(r - 1, c) // 상
    dfs(r + 1, c) // 하
    dfs(r, c - 1) // 좌
    dfs(r, c + 1) // 우
  };

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

  return islandCounts
}