[LeetCode] 1905. Count Sub Islands

https://leetcode.com/problems/count-sub-islands/description/?envType=daily-question&envId=2024-08-28

leetcode - Count Sub Islands

문제 유형 : bfs/dfs, 행렬

문제 난이도 : Medium

 

문제

You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Return the number of islands in grid2 that are considered sub-islands.

 

m x n의 크기의 행렬 grid1과 grid2가 주어진다. 0는 바다, 1은 땅을 의미한다.

1들이 4방향으로 인접해서 붙어있으면 하나의 섬으로 간주한다.

grid1의 섬에 부분집합인 grid2의 섬을 부분섬이라고 할 수 있다.

부분섬의 개수를 구하시오.

 

풀이

bfs / dfs를 통해서 섬을 구하는데, grid2를 기준으로 섬의 칸들을 방문하다가, grid1에서는 땅이 아닌 좌표에 방문하면, 부분섬이 될 수 없다.

bfs/dfs를 시작하는 기준은 grid1과 grid2 모두 땅인곳부터 시작해서, 

탐색 중에는 grid2의 값을 0으로 만들어서 물로 만들어서 재방문을 막는다.

bfs/dfs로 부분섬임이 확인되면, 카운터를 1 증가시킨다.

카운터의 값을 반환한다.

 

코드

C++ - BFS를 이용한 풀이

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    int m;
    int n;
    vector<int> dx;
    vector<int> dy;
    bool bfs(int r, int c, vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        bool flag = true;
        queue<pair<int, int>> q;
        q.push({r, c});

        while(!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if(grid2[nx][ny]) {
                    if(!grid1[nx][ny]) flag = false;
                    grid2[nx][ny] = 0;
                    q.push({nx, ny});
                }
            }
        }

        return flag;
    }
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        m = grid1.size();
        n = grid1[0].size();
        dx = {-1, 1, 0, 0};
        dy = {0, 0, -1, 1};
        
        int ans = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid1[i][j] && grid2[i][j]) {
                    if(bfs(i, j, grid1, grid2)) ans++;
                }
            }
        }
        
        return ans;
    }
};

 

GO - DFS를 이용한 풀이

var m, n int

func dfs(r, c int, grid1, grid2 [][]int) bool {
	if r < 0 || r >= m || c < 0 || c >= n || grid2[r][c] == 0 {
		return true
	}
	flag := grid1[r][c] == 1
	grid2[r][c] = 0
	flag = dfs(r-1, c, grid1, grid2) && flag
	flag = dfs(r+1, c, grid1, grid2) && flag
	flag = dfs(r, c-1, grid1, grid2) && flag
	flag = dfs(r, c+1, grid1, grid2) && flag

	return flag
}

func countSubIslands(grid1, grid2 [][]int) int {
	m = len(grid1)
	n = len(grid1[0])
	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid1[i][j] == 1 && grid2[i][j] == 1 {
				if dfs(i, j, grid1, grid2) {
					ans++
				}
			}
		}
	}
	return ans
}