[LeetCode 200. Number of Islands] C++ , C++로 전향하기로 결정했다.

회사 역량 시험은 C, C++, Java 만 가능한데, Java는 재귀 함수 사용 시 메모리 문제가 발생할 수 있다고 해서,

C++로 하기로 결정!!

 

Number of Islands 를 java로 다시 풀어보았다.

이전과 같이, DFS : Depth First Search 깊이 우선 탐색 알고리즘이며 재귀함수 호출 방식이다.

C++ 문법이 헷깔려서 다른 사람 코드를 언뜻 봤는데, 알고리즘이 좋아서 나도 참조해 보았다.

class Solution {
public:
    int r_length = 0;
    int c_length = 0;
    
    void findOne(vector<vector>& grid, int r, int c){
        if(r < 0 || r >= r_length || c < 0 || c >= c_length)
            return;
        
        if(grid[r][c] == '0')
            return;
        
        grid[r][c] = '0';
        
        findOne(grid, r, c-1);
        findOne(grid, r, c+1);
        findOne(grid, r-1, c);
        findOne(grid, r+1, c);
        
        return;
    }
    int numIslands(vector<vector>& grid) {
        r_length = grid.size();
        
        if(grid.size() == 0)
            return 0;
        c_length = grid[0].size();
        
        int cnt = 0;
        for(int i = 0; i < r_length; i++){
            for(int j = 0; j < c_length; j++){
                if(grid[i][j] == '1'){
                    cnt++;
                    findOne(grid, i, j);
                }
            }
        }
        
        return cnt;
    }
    
};

출처 : https://leetcode.com/problems/number-of-islands/discuss/266379/(98.93-100)-DFS-C%2B%2B