LeetCode 200 - Number of Islands (Medium)

문제

LeetCode - 200번

풀이 과정

섬의 개수를 세어주는 DFS 탐색 문제입니다.
간단한 문제이지만 히든 케이스 때문에 조금 헤맸습니다.

LeetCode 문제는 깔끔하지만 입력 제한 사항이 명시되어있지 않은 경우가 있어서 난감한 상황이 종종 발생하는 것 같습니다.
(입력으로 주어지는 grid 가 비어있는 경우가 존재할 것이라고 생각을 못했습니다..)

때문에 문제를 풀 때는 여러 edge case 를 고려하는 연습이 필요해보입니다.

코드

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  const dx = [0, 0, 1, -1];
  const dy = [1, -1, 0, 0];

  if (!grid.length) {
    return 0;
  }

  const N = grid.length,
    M = grid[0].length;
  const visit = new Array(N).fill(0).map((_) => new Array(M));

  function dfs(x, y) {
    visit[x][y] = 1;

    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i],
        ny = y + dy[i];
      if (0 <= nx && nx < N && 0 <= ny && ny < M) {
        if (!visit[nx][ny] && grid[nx][ny] === "1") {
          dfs(nx, ny);
        }
      }
    }
  }

  let ans = 0;
  for (let x = 0; x < grid.length; x++) {
    for (let y = 0; y < grid[0].length; y++) {
      if (!visit[x][y] && grid[x][y] === "1") {
        dfs(x, y);
        ans++;
      }
    }
  }

  return ans;
};

const grid = [
  ["1", "1", "0", "0", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "1", "0", "0"],
  ["0", "0", "0", "1", "1"],
];

console.log(numIslands(grid));