[Algorithm/java] NumberOfIsland

Problem

1은 육지, 0은 바다
육지의 개수를 구하시오.

Input
{'1','1','1','0','1'},
{'1','1','0','0','0'},
{'1','1','0','0','1'},
{'0','0','0','0','1'}

Output
3

전형적인 dfs 문제.

접근하기

1. 구구단처럼 행 별로 접근한다.
2. 1 or 0을 구별한다.
3. 1인 경우 위,아래,앞,뒤를 모두 1인지 0인지 확인한다.
4. 0인 경우, 멈추고 다음 탐색까지 계속 간다.

Code

public class NumberOfIsland {
    
    public static void main(String[] args){
        char[][] grid = {
                        {'1','1','1','0','1'},
                        {'1','1','0','0','0'},
                        {'1','1','0','0','1'},
                        {'0','0','0','0','1'}
                        };
        
        NumberOfIsland a = new NumberOfIsland();
        a.solve(grid);
    }
    
    
    public int solve(char[][] grid){
        print(grid);
        
        
        //1 error managing
        if(grid==null || grid.length==0 || grid[0].length==0) return 0;
        
        //2 [0,0]위치가 1인 것부터 찾는다.
        int count=0;
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[i].length; j++){
                if(grid[i][j]=='1'){
                    System.out.print("result count grid["+i+"]["+j+"]"+grid[i][j]+" ");
                    count++;
                    dfs(grid, i , j);
                }
            }
        }
        System.out.println("count"+count);
        print(grid);
        return count;
    }
    
    public void dfs(char[][] grid, int i, int j){
        System.out.println("i : "+i+"j :"+j);
        int m = grid.length;
        int n = grid[0].length;
        if(i<0 || i>=m || j<0 || j>=n || grid[i][j]!='1') return ;
        grid[i][j] = 'X';
        
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
        
    }
    
    public void print(char[][] grid){
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[i].length; j++){
                System.out.print(grid[i][j]+" ");
            }
            System.out.println();
        }
    }
}

print 메서드는 내가 임의로 로그값 확인해보려고 넣어둔 것이다.

📌 KeyNote

• 분리부터 하고 나중에 예외처리 하려고 하니 문제가 발생한다.
• 예외처리부터 먼저 하고 시작하자!