200. Number of Islands(two approach).md

Solution 1 dfs

• time O(mn) not O(mn*4^l)

public class Solution {
    public int numIslands(char[][] grid) {
        //int length = grid.length
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1') {
                    dfsUti(grid, i, j);
                    ++count;
                }
                
            }
        }
        
        return count;
    }
    //dts : make the 1 to 0
    public void dfsUti(char[][] grid,int i,int j) {
        //boundary case
        if(i < 0 || j < 0 || i>= grid.length || j >= grid[0].length  ) return;
        //the grid not belong to 'island'
        if(grid[i][j] != '1') return;
        
        grid[i][j] = '0';
        
        dfsUti(grid, i-1, j);
        dfsUti(grid, i, j-1);
        dfsUti(grid, i+1, j);
        dfsUti(grid, i, j+1);
    }
}


//approach 1: depth search: make the 1 to 0  
//approach 2: union find