[LeetCode] C++ 200. Number of Islands

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

 

문제

 

문제 분석

- 입력값을 동서남북이 모두 연결된 그래프로 가정하고 각 방향에 대해서 DFS 재귀를 이용해서 탐색이 끝나면 전체 섬의 개수를 1 증가시키는 방법으로 섬들을 탐지할 수 있습니다.

- 방문 여부를 따로 트래킹하거나 '1'을 '0'으로 바꾸는 방법을 사용할 수 있습니다.

 

풀이 1 (방문 여부 트래킹)

class Solution {
private:
    vector<vector<bool>> isVisited;
    vector<vector<char>> *grid;
    int row;
    int col;
    int count;

public:
    void dfs(int i, int j){
        if(i < 0 || j < 0 || i >= row || j >= col ||(*grid)[i][j] == '0'){
            return;
        }

        if(isVisited[i][j]){
            return;
        }else{
            isVisited[i][j] = true;
            dfs(i+1, j);
            dfs(i-1, j);
            dfs(i, j+1);
            dfs(i, j-1);
        }

    }

    int numIslands(vector<vector<char>>& grid) {
        this->grid = &grid;
        row = grid.size();
        if(row == 0)
            return 0;
        col = grid[0].size();

        count = 0;

        isVisited = vector<vector<bool>>(row, vector<bool>(col, false));

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == '1' && !isVisited[i][j]){
                    dfs(i,j);
                    count++;
                }
            }
        }

        return count;
    }
};

 

풀이 2 ('1'을 '0'으로 변경)

class Solution {
private:
    vector<vector<char>> *grid;
    int row;
    int col;

public:
    void dfs(int i, int j){
        if(i < 0 || j < 0 || i >= row || j >= col || (*grid)[i][j] == '0'){
            return;
        }

        (*grid)[i][j] = '0';

        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }

    int numIslands(vector<vector<char>>& grid) {
        this->grid = &grid;
        row = grid.size();
        if(row == 0)
            return 0;
        col = grid[0].size();

        int count = 0;

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == '1'){
                    dfs(i, j);
                    count++;
                }
            }
        }

        return count;
    }
};