Number of Islands (DFS)

예전에 LeetCode에서 Queue를 공부할 때 Number of Islands라는 문제를 푼 적이 있다.

2020/07/21 - [알고리즘/LeetCode] - Number of Islands using BFS

Number of Islands using BFS

그때는 문제에서도 Queue 자료구조를 활용한 BFS를 요구했기 때문에 이를 활용했지만 최근 다시 공부하면서 풀이를 되새겨보니 꼭 이를 사용하지 않아도 문제를 풀 수 있을 것 같아 풀이를 조금 바꿔보았다.

class Solution {    
    public int numIslands(char[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int numOfIslands = 0;
        
        for(int row=0;row<rows;row++){
            for(int col=0;col<cols;col++){
                if(grid[row][col] == '0') continue;
                numOfIslands++;
                BFS(grid, row, col, cols, rows);
            }
        }
        
        return numOfIslands;
    }
    
    private void DFS(char[][] map, int y, int x, int width, int height){
            map[y][x] = '0';
            
            if(y > 0 && map[y-1][x] == '1'){
                DFS(map, y-1, x, width, height);
            }
            
            if(x > 0 && map[y][x-1] == '1'){
                DFS(map, y, x-1, width, height);
            }
            
            if(y < height - 1 && map[y+1][x] == '1'){
                DFS(map, y+1, x, width, height);
            }
            
            if(x < width - 1 && map[y][x+1] == '1') {
                DFS(map, y, x+1, width, height);            
            }
    }
}

지난번과는 달리 BFS가 아닌 DFS를 사용했다. 그렇기 때문에 Queue를 사용할 필요가 없었으며 위, 왼쪽, 아래, 오른쪽 셀 순서로 재귀 함수를 호출하는 방식으로 구현했다. 그리고 굳이 방문했던 셀을 기억하는 자료구조가 필요 없을 것 같아서 삭제하고 대신 방문한 셀의 값을 '0'으로 바꿔주는 방식으로 표시해두었다. 문제 특성상 섬을 측정할 때 셀을 대각선으로 이동하지 않고 수평, 수직 방향으로만 이동하기 때문에 잘못 측정할 일은 없으며 약간 땅따먹기처럼 섬('1')을 갉아먹어서 '0'으로 만드는 로직이다.

 

확실히 Queue나 다른 자료구조를 안쓰니까 속도는 빨라졌는데 여전히 메모리 사용량에서는 낮은 성능(42000KB)을 보이고 있다. 무엇이 문제인지 확인하기 위해 40800KB의 메모리를 사용하는 설루션을 분석해보았다.

class Solution {
    public int numIslands(char[][] grid) {
        if(grid.length == 0) return 0;
        int row = grid.length;
        int col = grid[0].length;
        int count = 0;
        for (int i = 0; i<row; i++) {
            for (int j = 0; j<col; j++) {
                if(grid[i][j] == '1'){
                    DFS(grid, i, j, row, col);
                    count++;
                }
            }
        }
        return count;
    }
    
    private void DFS(char[][] grid, int i, int j, int row, int col){
        if(i<0||j<0||i>=row||j>=col||grid[i][j]=='0') return;
        grid[i][j] = '0';
        DFS(grid,i-1,j,row,col);
        DFS(grid,i+1,j,row,col);
        DFS(grid,i,j-1,row,col);
        DFS(grid,i,j+1,row,col);
    }
}

대체적으로 비슷하지만 DFS 함수에서 일단 재귀적으로 호출하고 함수 첫 문장에서 부적절한 셀을 참조하는지 검사하고 있다. 내가 작성했던 코드처럼 매 호출마다 일일히 검사하는 것보다는 이렇게 호출 시작 시 인덱스 자체만 비교하는 방법도 괜찮은 것 같다.

 

재밌는 점은 좀 성능이 잘 나온다 싶은 해결 방법은 대부분 DFS를 사용하고 있다는 점이다. BFS와 Queue를 활용해서 문제를 풀라고 했지만 고득점을 위해서 DFS로 문제를 푸는 모습을 보니 좀 묘한 감이 없지 않아 있다.