[Leetcode] 200. Number of Islands - JS

https://leetcode.com/problems/number-of-islands/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
1(땅), 0(물)의 지도를 나타내는 m x n 이진 그리드가 주어질 때,
섬의 갯수를 반환하라.
섬은 물로 둘러싸여 있고 인접한 육지가 수평 또는 수직으로 연결되어 형성된다.

제한조건
--------------------
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j]는 '0', '1' 이다.

 

2. 접근 방법 - DFS

접근방법
--------------------
DFS(깊이우선탐색)으로 접근한다.
현재 요소가 '1'이면, 섬에 방문한 것으로 카운트 값 증가시킨다.
현재 요소와 인접한 요소 그리고 그 인접한 요소와 인접한 요소들까지 재귀적으로 DFS 탐색한다.
재귀적으로 인접한 요소들을 탐색하면서 해당 요소들을 방문처리하지 않기 위해 '0'값으로 수정한다.
그러면 이후의 요소 순회시 방문했던 섬들은 모두 '0'으로 표시되므로 섬 갯수를 증가시키지 않는다.

 

 

3. 코드

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let count = 0;
    let rows = grid.length;
    let cols = grid[0].length;

    function dfs(row, col) {
    	// 배열 범위 벗어나거나 '0'이면 패스
        if (row < 0 || 
            row >= rows || 
            col < 0 || 
            col >= cols || 
            grid[row][col] === '0'
        ) return;

        grid[row][col] = '0'

        dfs(row - 1, col); // 위
        dfs(row + 1, col); // 아래
        dfs(row, col - 1); // 왼쪽
        dfs(row, col + 1); // 오른쪽
    }

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(i, j);
            }
        }
    }
    
    return count;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(m * n)

- 공간복잡도: O(m * n)

 

행열을 중첩 반복문으로 순회하여 접근하는 것 까진 알겠는데, 이미 방문한 섬을 어떻게 처리해야할지 떠오르지 않아서 Claude의 도움을 받았다.

DFS 탐색하여 현재 요소와 인접한 모든 요소들을 방문 처리해주는 방식을 배웠다.

Binary Tree(이진트리) 문제를 풀면서 재귀함수 호출하는 방식으로 DFS를 구현하는 것을 배웠는데, 다시 또 까먹은 것 같다..

풀었던 문제들도 다시 반복해서 풀어봐야겠다.

 

 

5. BFS 방법 풀이

BFS(너비 우선 탐색)으로도 풀어보자.

 

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let count = 0;
    let rows = grid.length;
    let cols = grid[0].length;

    function bfs(row,col) {
        const queue = [[row, col]];
        const directions = [[-1,0], [1,0], [0,-1], [0,1]];

        grid[row][col] = '0';

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

            for (const [dx, dy] of directions) {
                const newRow = currentRow + dx;
                const newCol = currentCol + dy;

                if (newRow < 0 || 
                    newRow >= rows || 
                    newCol < 0 || 
                    newCol >= cols || 
                    grid[newRow][newCol] === '0') {
                    continue;
                }

                grid[newRow][newCol] = '0';
                queue.push([newRow, newCol])
            }
        }
    }

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                count++; // 새로운 섬 발견
                bfs(i, j); // BFS로 연결된 모든 땅 방문
            }
        }
    }
    
    return count;
};

 

DFS와 다르게 재귀함수를 사용하지 않고 queue 자료구조를 사용하여 인접한 요소의 좌표값을 queue에 추가하면서 directions를 통해 상하좌우 인접한 요소들을 확인하여 인접한 요소들을 '0'으로 바꿔 방문처리 해주었다.

6. DFS vs BFS

구분	DFS	BFS
탐색방식	- 한 방향으로 끝까지 탐색 후 다음 방향 탐색 - 재취 호출 사용 - 스택 메모리 사용	- 현재 위치에서 가까운 곳부터 순차적으로 탐색 - queue 사용 - 힙 메모리 사용
장점	- 구현 간단하다. - 경로 탐색 시 유리하다. - 일반적으로 메모리 사용량이 적다	- 최단 경로 찾기 유리하다. - 레벨 단위 탐색 시 유리하다. - 스택 오버플로우 위험 없다.
단점	- 재귀 호출로 스택 오버플로우 가능성 존재 - 최단 경로 찾기 어려움	- queue 관리로 추가 메모리 사용 - DFS보다 구현 복잡
시간복잡도	O(rows * cols)	O(rows * cols)
공간복잡도	O(rows * cols)	O(min(rows, cols))

 

DFS와 BFS를 비교해서 두 가지 풀이 방법으로 풀어보니 탐색방식과 장단점을 이해하는데 도움이 됐다.