[C++] LeetCode : Number of Islands

Question

Given an m x n 2D binary grid [grid] which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

m x n 인 2차원 grid가 주어진다. grid의 1은 땅, 0은 물을 의미할 때 island의 개수를 세라. island는 물로 상하좌우가 둘러싸인 땅을 의미한다.

 

제약사항

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid [i][j]is '0' or '1'.

---

Solution

문제를 풀 때 고려한 사항

• 주어진 맵의 크기가 1x1일 때 알고리즘이 정상 동작해야 한다. 

---

Solution

가장 쉽게 생각할 수 있는 방법은 BFS이다.

class Solution {
public:
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        queue<pair<int,int>> land;
        vector<vector<int>> visit(m, vector<int> (n));

        int land_count = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == '1' && visit[i][j] == 0){
                    land.push({i,j});

                    land_count++;
                    while(!land.empty()){
                        pair<int,int> l = land.front();
                        land.pop();

                        visit[l.first][l.second] = land_count;
                        for(int k=0; k<4;k++){
                            int next_x = l.first + dx[k];
                            int next_y = l.second + dy[k];

                            if(next_x <0 || next_y<0 || next_x>=m || next_y>=n) continue;
                            if(grid[next_x][next_y] != '1' || visit[next_x][next_y]) continue;
                            
                            visit[next_x][next_y] = land_count;
                            land.push({next_x, next_y});
                        }
                    }
                }
            }
        
        }

        return land_count;
    }
};

• Time complexity : O(nm) 
• Space Complexity : O(nm) 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/792/

Explore - LeetCode