LeetCode - Number of Islands

문제 설명

Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

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

Example 2:

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

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

Solution

• DFS 알고리즘 사용
• 배열을 순환하며 탐색되지 않은 항목 발견시, 상하좌우로 DFS 탐색

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

    for (let i = 0; i < rowLen; i++){
        for (let j = 0; j < colLen; j++){

            if (grid[i][j] == '1') { // 탐색되지 않은 항목 발견
                count++;
                dfs(grid,i,j,rowLen,colLen);
            }// 0,2 일결우는 다음으로 넘어감
        }
    }
    return count;
};

var dfs = function (grid, i, j,rowLen,colLen) {

    grid[i][j] = '2'; // 탐색된 항목의 경우 1을 2로 바꿔주어 두번 탐색하지 않도록 함
    if (i > 0 && grid[i - 1][j] == '1') { // 상
        dfs(grid, i - 1, j, rowLen, colLen);
    }
    if (i < rowLen - 1 && grid[i + 1][j] == '1') { // 하
        dfs(grid, i + 1, j, rowLen, colLen);
    }

    if (j > 0 && grid[i][j - 1] == '1') { // 좌
        dfs(grid, i, j - 1, rowLen, colLen);
    }

    if (j < colLen-1 && grid[i][j + 1] == '1') { // 우
        dfs(grid, i, j + 1, rowLen, colLen);
    }

};

~.~