[LeetCode] Number Of Islands

2차원 배열이 주어진다. 그 안에는 '1'과 '0'으로 채워져있고 0은 물이고 1은 육지다.
따라서 2차원 배열내에 존재하는 섬의 개수를 구하는 문제다.

재귀로 문제를 해결하면 되겠다.

라는 생각이 제일 먼저 들었다.

cheked를 만들어 방문했는지 방문하지 않았는지를 판별하고 재귀로 확인해보면 되겠구나
라는 문제 풀이 방법1

두 번째 풀이 방법은 각각의 지점들을 그래프화 해서 각각의 Vertex를 DFS 하면 되겠구나 라는 문제 풀이 방법2

문제풀이방법2는 좀 더 복잡해 질 것 같아, 직관적인 문제 풀이 방법1을 선택

class Solution {
    
    boolean[][] checked;
    char[][] grid;
    
    public int numIslands(char[][] grid) {
        int answer=0;
        if(grid.length==0) return 0;
        checked=new boolean[grid.length][grid[0].length];
        this.grid = grid;
        
        for(int x=0; x<grid.length; x++){
            for(int y=0; y<grid[x].length; y++){
                if(checked[x][y]==true) continue;
                if(grid[x][y]=='0') continue;
                answer++;
                checkIsland(x,y);
            }
        }
        return answer;
    }
    
    public void checkIsland(int x,int y){
        if(grid[x][y]=='0') return;
        if(checked[x][y]==true) return;
        checked[x][y]=true;
        if(x!=0) checkIsland(x-1,y);
        if(x!=grid.length-1) checkIsland(x+1,y);
        if(y!=0) checkIsland(x,y-1);
        if(y!=grid[0].length-1) checkIsland(x,y+1);
    }
}

해결

처음에 메모리 사용량이 17프로에 미치는 안좋은 결과를 보고
전역변수화해서 각 함수에 넘기는 스택 메모리를 최소화 하니 결과가 훨씬 더 좋게 나오는 것을 볼 수 있었다.

암튼 문제 자체는 쉬웠다.

다만 여기서 속도를 좀 더 높일 수 있는 방법이 있을까 하는 궁금증은 든다.