[leetcode 200] Number of Islands

Given an m x n 2d grid 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.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

문제 풀이:

백준에서도 자주 본 bfs/dfs 이용 문제이다.

배열이 1이면 bfs에 진입하여 인접해있는 모든 1을 방문 체크. 섬의 개수를 하나 늘린다.

 

-첨에 tle가 났었는데 visited배열을 따로 만들어주지 않고 바로 grid에 체크를 했을 때 발생했다. visitied배열을 따로 만들어주자.

class Solution {
public:
    
    int numIslands(vector<vector<char>>& grid) {
        int result = 0;
        
        int m = grid.size();
        int n = grid[0].size();
       
        int drow[4] = {0,0,-1,1};
        int dcol[4] = {1,-1,0,0};
        
        int visited[301][301] = {0,};
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == '1' && !visited[i][j]){
                    queue<pair<int, int>>q;
                    q.push(make_pair(i,j));
                    visited[i][j] = 1;
                    result++;
                    
                    while(!q.empty()){
                        int row = q.front().first;
                        int col = q.front().second;
                        
                        q.pop();
                        
                        for(int k=0; k<4; k++){
                            int nRow = row + drow[k];
                            int nCol = col + dcol[k];
                            
                            if(nRow > -1 && nRow < m && nCol > -1 && nCol < n){
                               
                                if(visited[nRow][nCol] || grid[nRow][nCol]!='1') continue;
                                    
                                q.push(make_pair(nRow, nCol));
                                visited[nRow][nCol] = 1;
                                
                            }
                        }
                    }
                }
            }
        }
        
        return result;
    }
};