LeetCode - Number of Enclaves (Javascript)

문제 설명

오로지 바다(0)에 둘러싸인 육지(1)의 개수를 구하는 문제다.

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid *for which we cannot walk off the boundary of the grid in any number of moves*.

Example 1:

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.

Example 2:

Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: All 1s are either on the boundary or can reach the boundary.

Constraints:

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

---

소스 코드

이전 문제들과 비슷한 로직이라서 푸는데 큰 어려움이 있지는 않았다 🙂

const numEnclaves = (grid) => {
  let answer = 0;
  let current;
  const rowLength = grid.length;
  const colLength = grid[0].length;
  for (let i = 0; i < rowLength; i++) {
    for (let j = 0; j < colLength; j++) {
      current = grid[i][j];
      if (!current) continue;
      if (!i || !j || i === rowLength - 1 || j === colLength - 1) {
        dfs(i, j);
      }
    }
  }

  for (let i = 1; i < rowLength - 1; i++) {
    for (let j = 1; j < colLength - 1; j++) {
      if (grid[i][j] === 1) answer++;
    }
  }

  function dfs(i, j) {
    if (grid[i] === undefined || grid[i][j] === undefined || !grid[i][j]) {
      return;
    }
    grid[i][j] = 0;
    dfs(i - 1, j); // up
    dfs(i, j + 1); // right
    dfs(i + 1, j); // down
    dfs(i, j - 1); // left
  }

  return answer;
};

---

풀이 설명

테두리에 있는 섬(1)만을 처음 반복문에서 체크한다.
그리고 해당 테두리를 기점으로 연결되어 있는 섬들을 모두 0으로 치환해준다.

그렇게 테두리를 기점으로 연결되어 있는 섬들이 제거된 뒤에, 다음 반복문을 통해 아직 남아있는 섬(1)들을 카운팅 해준다. (여기서 체크되는 섬(1)들은 테두리를 기점으로 하는 섬과 연결된 섬이 아니기 때문)

---