feat: [Med.] Number of Islands (JS/TS)

https://leetcode.com/problems/number-of-islands/description/

1. 문제분석
300 x 300 matrix -> 0 또는 1 -> 인접한 1은 한 덩어리 -> 덩어리의 개수 리턴

2. 풀어보기
덩어리를 찾아서 전체 개수를 계산
[1,1,1,1,0] -> 1개
[1,1,0,1,0]
[1,1,0,0,0]
[0,0,0,0,0]
[1,1,0,0,0] -> 3개
[1,1,0,0,0]
[0,0,1,0,0]
[0,0,0,1,1]

3. 슈도코드
land를 돌려서 -> dfs/bfs로 인접영역의 개수를 센다 (체크된 1은 0 처리)

 

4. 구현코드

const numIslands = (grid: string[][]): number => {
  let count = 0;

  for (let x = 0; x < grid.length; x++) {
    for (let y = 0; y < grid[x].length; y++) {
      if (grid[x][y] === '1') {
        byDfs(grid, x, y);
        // byBfs(grid, x, y);
        count++;
      }
    }
  }

  return count;
};

const DIRECTION = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

const byDfs = (grid: string[][], x: number, y: number) => {
  const stack: [number, number][] = [[x, y]];

  while (stack.length > 0) {
    const [x, y] = stack.pop()!;

    if (grid[x]?.[y] === '1') {
      grid[x][y] = '0';

      for (const [move_x, move_y] of DIRECTION) {
        if (grid[x + move_x]?.[y + move_y] === '1') {
          stack.push([x + move_x, y + move_y]);
        }
      }
    }
  }
};

const byBfs = (grid: string[][], x: number, y: number) => {
  const queue: [number, number][] = [[x, y]];
  let first = 0;

  while (first < queue.length) {
    const [x, y] = queue[first++];

    if (grid[x]?.[y] === '1') {
      grid[x][y] = '0';

      for (const [move_x, move_y] of DIRECTION) {
        if (grid[x + move_x]?.[y + move_y] === '1') {
          queue.push([x + move_x, y + move_y]);
        }
      }
    }
  }
};

 

5. 풀이회고

석유 시추 문제의 일부분에 불과한 문제였다. 겸사겸사 미뤘던 DFS를 루프&스택 기반으로 전환 정도만 추가로 해둔다.