[ leetcode ] dfs 문제 - number of islands

다시 한번 DFS 개념을 집고 넘어가자!
- 0번째 노드에서 이제 깊이 인접한 노드를 다 도는 방식으로 / stack 처럼 안에 넣었다가 지나갔으면 빼고 약간 이런식으로 동작함.


여기서 이제 궁금한 것. dfs 로 문제 풀기!
if ( grid[i][j] == '1') 로서 이제 그게 1 일 경우에만 지나갈 수 있도록 설정!!
- 이 1로서 설정하는 것은 이제 해당 내용의 값이 1 일 경우에 즉 땅일 경우에만 돌아가면 되기 때문..! 물인데 굳이 돌 필요 없자나?

1st Try -- checked 랑 언제 빠져나가야할지 고민...

class Solution {
    

    //x 좌표, y 좌표로 돌아가면서 간다고 생각해야함 
    // 섬을 찾아서 이게 연결된 곳이 없을 때까지 계속 돌아가면서 찾아간다. 
    static boolean checked[][] = new boolean[300][300];
    public boolean dfs(int x, int y) {
        if(checked[x][y]) {
            return false;
        }
        else {
            checked[x][y] = true;
            dfs(x, y-1);
            dfs(x, y+1);
            dfs(x-1, y);
            dfs(x+1, y);
            return true;    
        } 
        
        
    }
    // dfs 에서 핵심은 이제 어디 check 된 애들이지 확인 
    
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int number = 0;
        
        for(int i=0; i<m; i++) {
            int n = grid[i].length;
            //여기서 dfs 함수 호출하면 될듯 싶은데 
            for(int j=0; j<n; j++) {
                //여기서 각각 도는 함수를 호출 
                if(dfs(i,j))
                    number++;
            }
        }
        
        return number;
    }
    
}

dfs 로 풀기

class Solution {
    public int numIslands(char[][] grid) { 
        if(grid == null || grid.length == 0 || grid[0].length == 0 ) 
            return 0;
        
        int m = grid.length;
        int n = grid[0].length;
        
        int count = 0;
        for(int i = 0 ; i <m ; i++ )
        {
            for(int j = 0; j < n ; j++ )
            {
                if(grid[i][j] == '1') {
                    count++;
                    merge(grid, i , j);                
                }
            
            }
        }
        
        return count;
        
    }
    
    public void merge(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        
        if(i<0 || j< 0 || i>=m || j>=n || grid[i][j] != '1' )
            return;
        
        grid[i][j] = 'X';
        
        merge(grid, i-1, j);
        merge(grid, i+1, j);
        merge(grid, i, j-1);
        merge(grid, i, j+1);
        
    }
}