Leetcode - 200. Number of Islands

문제

mxn크기의 2차원 배열이 주어지고 '1'로 이루어진 영역은 섬을 의미하고 '0'은 바다를 의미한다. 섬의 총 갯수를 구하라.

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

https://leetcode.com/problems/number-of-islands/

해결 O(m x n) / O(m x n)

https://velog.io/@soopsaram/Leetcode-733.-Flood-Fill 문제와 거의 유사.

class Solution {
    int rsize;
    int csize;
    int **visited;
    bool check_island(vector<vector<char>>& grid, int sr, int sc) {
        
        if (sr < 0 || sr >= rsize || sc < 0 || sc >= csize)
            return false;
        if (grid[sr][sc] == '0')
            return false;
        if (visited[sr][sc] == 1)
            return false;
        
        visited[sr][sc] = 1;
        grid[sr][sc] = '0';
        check_island(grid, sr-1, sc);
        check_island(grid, sr+1, sc);
        check_island(grid, sr, sc-1);
        check_island(grid, sr, sc+1); 
        return true;
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        rsize = grid.size();
        csize = grid[0].size();
        int nr_island = 0;
        visited = (int **)calloc(rsize, sizeof(int *));
        for (int i = 0; i < rsize; i++)
            visited[i] = (int *)calloc(csize, sizeof(int));
        
        for (int i = 0; i < rsize; i++) {
            for (int j = 0; j < csize; j++) {
                if (check_island(grid, i, j))
                    nr_island++;
            }
        }
        return nr_island;
    }
};