LeetCode - Number of Closed Islands (Javascript)

Description

1이라는 물에 둘러싸인 0이라는 섬의 개수를 구하는 문제다.

Given a 2D grid consists of 0s (land) and 1s (water).  An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

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

Example 3:

Input: grid = [[1,1,1,1,1,1,1],
               [1,0,0,0,0,0,1],
               [1,0,1,1,1,0,1],
               [1,0,1,0,1,0,1],
               [1,0,1,1,1,0,1],
               [1,0,0,0,0,0,1],
               [1,1,1,1,1,1,1]]
Output: 2

---

소스코드

function closedIsland(grid) {
  let answer = 0;
  let temp = 1;
  // 행과 열의 끝 부분을 maxRow와 maxCol로 지정
  const maxRow = grid.length - 1;
  const maxCol = grid[0].length - 1;
  // 헬퍼함수 traverse
  function traverse(r, c, grid) {
    // 현재 섬이 유효하지 않은 섬이거나(범위 밖), 1일 경우에는 재귀를 종료시킨다.
    if (grid[r] === undefined || grid[r][c] === undefined || grid[r][c] === 1)
      return;
    // 이 아래부터는 위의 조건문에 의해 모든 노드가 0일 때다.
    // r이 0이거나, 행의 끝에 닿았으면 -> 갇힌 섬이 아니다. (c또한 마찬가지)
    if (r === 0 || r >= maxRow || c === 0 || c >= maxCol) {
      // 따라서 temp에 0을 할당해준다.
      temp = 0;
    }
    // 그리고 효율성을 위해 매 순회마다 0인 섬을 1로 변환시켜준다.
    grid[r][c] = 1;
    traverse(r - 1, c, grid); //상
    traverse(r, c + 1, grid); //우
    traverse(r + 1, c, grid); //하
    traverse(r, c - 1, grid); //좌
  }
  // 1. 우선 모든 grid를 탐색하기 위한 2중 for문을 아래와 같이 생성했다.
  for (let i = 1; i <= maxRow; i++) {
    for (let j = 1; j <= maxCol; j++) {
      // 효율성을 위해 i가 마지막 행일 때, j가 마지막 열일 때는 무시하도록 설정했다.
      if (i === maxRow || j === maxCol) continue;
      // temp는 매 반복마다 1로 초기화 한다.
      temp = 1;
      // 그리고 순회를 하다가, 노드가 0인 경우 헬퍼 함수를 실행시킨다.
      if (grid[i][j] === 0) {
        traverse(i, j, grid);
        // traverse가 끝났는데도 여전히 temp가 1이라면 갇혀있는 섬이라는 뜻이다.
        if (temp !== 0) answer++;
      }
    }
  }
  return answer;
}

소스코드 (주석 제거)

function closedIsland(grid) {
  let answer = 0;
  let temp = 1;
  const maxRow = grid.length - 1;
  const maxCol = grid[0].length - 1;

  function traverse(r, c, grid) {
    if (grid[r] === undefined || grid[r][c] === undefined || grid[r][c] === 1)
      return;
    if (r === 0 || r >= maxRow || c === 0 || c >= maxCol) temp = 0;
    grid[r][c] = 1;
    traverse(r - 1, c, grid);
    traverse(r, c + 1, grid);
    traverse(r + 1, c, grid);
    traverse(r, c - 1, grid);
  }

  for (let i = 1; i <= maxRow; i++) {
    for (let j = 1; j <= maxCol; j++) {
      if (i === maxRow || j === maxCol) continue;
      temp = 1;
      if (grid[i][j] === 0) {
        traverse(i, j, grid);
        if (temp !== 0) answer++;
      }
    }
  }
  return answer;
}

---