[LeetCode] 200. Number of Islands, Medium

1. 문제

• m x n 크기의 2차원 배열이 주어지고, 각 요소는 1(섬), 0(바다)로 구성되어 있을 때, 존재하는 섬의 개수를 반환하라.
• 섬은 수직 또는 수평으로 다른 인접한 섬을 가지고 있고, 바다로 둘러쌓여 있다. (모서리는 바다로 가정)

2. 해결

const row = [-1, 1, 0, 0];
const col = [0, 0, -1, 1];

function DFS(grid, x, y) {
    if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] === '0') return;

    grid[x][y] = '0'

    for(let k=0; k< 4; k++) {
        const adjustX = x + row[k] , adjustY = y + col[k];

        DFS(grid, adjustX, adjustY)
    }

}

function numIslands(grid: string[][]): number {
    const queue = new Array();
   
    let count = 0;

    for(let i=0; i<grid.length; i++) {
        for(let j =0; j< grid[i].length; j++){
            if (grid[i][j] === '1') {
                // count++;
                // DFS(grid, i, j)
                queue.push([i,j]);

                while(queue.length > 0) {
                    const [x,y] =queue.shift();

                    for(let k=0; k< 4; k++) {
                        const adjustX = x + row[k] , adjustY = y + col[k];

                        if(adjustX >= 0 && adjustX < grid.length && adjustY >=0 && adjustY < grid[i].length && grid[adjustX][adjustY] === '1') {
                            grid[adjustX][adjustY] = '0'
                            queue.push([adjustX, adjustY]);
                        }
                    }
                }

                count++;
            }
        }
    }

    return count;
};

• 4년전에 공부했던 BFS 챕터 문제이다. 
• BFS는 큐를 이용할 수 있고, DFS는 스택을 이용할 수 있다. 내가 알기론 다른 방법으로도 구현이 가능하지만, 최대한 큐, 스택을 활용해 보려 한다.
• 원리는 0,0 부터 탐색하여 섬인 경우, 큐에 넣어 BFS 탐색을 수행한다. 
  • 시작 노드를 큐에 넣는다.
  • 큐에서 뺀 후, 인접 노드를 탐색한다.
  • 조건에 맞으면, 방문처리 후 큐에 넣는다.
  • 큐가 비어질 때 까지 해당 조건에 맞는 노드를 탐색한다.
• 1인 경우 섬을 발견했으므로 count를 증가시키고 DFS 탐색 시작.
  • 종료조건을 세우고 방문 처리.
  • 인접한 노드를 재귀 호출 반복하며 0으로 바꿨으므로 방문 처리.