200. Number of Islands, 1254. Number of Closed Islands, 1020. Number of Enclaves (dfs, bfs) 문제

단계적으로 풀기 좋은 dfs, bfs 문제가 있어 같이 포스팅 하게 되었다.

<의역>: mxn 만큼의 '1'(땅) '0'(물)로 이루어진 이차원 char 배열이 있을 때  1이 존재하는 공간(땅)의 갯수를 반환 하라.

단 연속적으로 이어진 공간은 한 개의 땅으로 인정한다.  

 

<접근법>

이차원 배열을 순차적으로 탐색하여 '1'인 곳을 반견하면 땅의 갯수+1

그리고 해당 지점을 기준으로 dfs로 탐색하여 '1'인 곳은 방문 했다는 표시를 하고

각 방향에서 '0'이 나오거나 배열의 범위의 맨 끝에 도달하면 return 

 

<코드>

class Solution {
    public void dfs(char[][] grid,int i, int j){
        if(i<0||i>= grid.length||j<0||j>=grid[0].length)
            return;
        if(grid[i][j]=='0')
            return;
        grid[i][j]='0';
        
        dfs(grid, i+1, j); dfs(grid, i-1, j);
        dfs(grid, i, j+1); dfs(grid, i, j-1);
    }
    public int numIslands(char[][] grid) {
        int count=0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]=='1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
}

<의역>: 위에 문제에서 한 가지 조건이 추가 단순히 땅의 갯수를 반환 하는 것이 아니라

상하좌우가 전부 물로 둘러 싸인 섬의 갯수를 반환 

 

<접근법>

해당 문제의 값이 땅은 0이고 물은 1임을 이용하여 

이차원배열을 순차적으로 탐색할 때 해당 값이 0이면 그 점을 기준으로 dfs 하여

벽이라면 0, 그렇지 않으면 1을 반환하도록 하고 방문한 땅을 표시

그 후 상하좌우 4방향에 탐색한 결과값을 곱하여 반환

(만약 주변에 벽이 있다면 0, 물로만 둘러 싸여 있다면 1이 반환될 것)

 

<코드>

class Solution {
    // 시간 복잡도 O(n*m) 공간 복잡도 O(n*m)
    public int dfs(int[][] grid,int i,int j){
        if(i<0||i>=grid.length||j<0||j>= grid[0].length)
            return 0;
        if(grid[i][j]>0)
            return 1;
        grid[i][j] = 2;

        return dfs(grid, i+1, j)*dfs(grid, i-1, j)*dfs(grid, i, j+1)*dfs(grid, i, j-1);
    }
    public int closedIsland(int[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]==0)
                    count+=dfs(grid,i,j);
            }
        }
        return count;
    }
}

<의역>: 바로 위에 있던 1254번 문제에서 섬의 갯수를 반환 했다면 이제는 섬을 구성하는 cell의 갯수를 반환 할 것 

 

<접근법>

마찬가지로 이차원 배열을 순차적으로 탐색하되 해당 값이 1 이라면 해당 값을 기준으로 dfs 탐색 

해당 공간이 땅이라면 1을 반환하고 그렇지 않으면 0을 반환 만약 배열의 범위 끝에 맞닿는 다면 벗어 놨다면 따로 변수를 통해 섬이 아님을 표시 + 각각 방문한 땅을 표시 

종합적으로 해당 영역이 섬이 아닐 경우

해당 cell에서 상하좌우의 땅의 수를 모두 더해 반환

 

<코드>

class Solution{
    private boolean isIsland = true;
    public int dfs(int [][] grid,int i,int j){
        int count = 0;
        if(i<0||i>= grid.length||j<0||j>=grid[0].length) {
            isIsland = false;
            return 0;
        }
        if(grid[i][j]<1)
            return 0;

        if(grid[i][j]==1) {
            grid[i][j]=-1;
            count=1;
        }

        int[][] fourWay = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int[] way:fourWay) {
            count += dfs(grid,i+way[0],j+way[1]);
        }

        return count;
    }
    public int numEnclaves(int[][] grid) {
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]==1) {
                    int tmp = dfs(grid, i, j);
                    if(isIsland)
                        ans+=tmp;
                    isIsland = true;
                }
            }
        }
        return ans;
    }
}