[LeetCode] 1020. Number of Enclaves - Java

https://leetcode.com/problems/number-of-enclaves/

Number of Enclaves - LeetCode

---

문제

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

 

Example 1:

 

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.

Example 2:

 

Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: All 1s are either on the boundary or can reach the boundary.

Constraints:

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

 

---

풀이

풀이 과정

각 셀이 바다(0)와 땅(1)으로 이루어진 m x n 크기의 2차원 배열 grid가 주어질 때 사방이 바다로 둘러 쌓인 땅 타일의 개수를 구하는 문제이다.

각 타일을 탐색할 때에 사용할 함수를 먼저 생성한다.

탐색 대상 그리드와 행과 열의 인덱스, 그리고 현재 탐색중인 타일이 바다로 쌓여있는지 여부를 전달받는다.
우선 탐색 대상 좌표가 그리드를 벗어나는 경우에는 바로 탐색을 종료한다.
탐색 대상 좌표가 그리드 내에 있는 경우에는 현재 타일이 땅 타일인지 여부를 판단한다.
땅 타일인 경우에는 현재 타일을 바다로 변경하고 바다로 쌓여 있는지 여부에 따라 정답카운트를 증가시킨다.
그 후 상하좌우에 연결되어있는 타일을 탐색하며 모든 인접한 땅타일을 바다로 변경하며 같은 과정을 반복한다.

/**
 * @param grid  탐색 대상 그리드
 * @param row   현재 탐색중인 행의 인덱스
 * @param col   현재 탐색중인 열의 인덱스
 * @param inEnclosed 현재 탐색중인 타일이 물로 쌓여있는지 여부
 * @return
 */
public void dfs(int[][] grid, int row, int col, boolean isEnclosed){
    // 좌표가 그리드를 벗어나는 경우 탐색 종료
    if(row < 0 || col < 0 || row >= grid.length || col >= grid[0].length) return;
    // 방문한 타일이 땅(1)인 경우 물(0)로 변경
    // 물로 둘러 쌓여있는 땅 타일인 경우 정답 카운트 증가
    // 상하좌우 타일 탐색하며 모든 인접한 땅타일을 물로 변경
    if(grid[row][col] == 1){
        grid[row][col] = 0;
        if(isEnclosed) answer++;
        dfs(grid, row, col+1, isEnclosed);
        dfs(grid, row, col-1, isEnclosed);
        dfs(grid, row+1, col, isEnclosed);
        dfs(grid, row-1, col, isEnclosed);
    }
}

 

해당 함수를 사용하여 그리드의 모든 셀을 탐색하는데 땅타일이 그리드의 가장자리까지 연결되어있는 경우 연결된 땅 타일들은 바다로 둘러쌓여있지 않는것으로 간주되므로 우선 그리드의 가장자리부터 isEnclosed를 false로 탐색하여 바다로 둘러쌓여있지 않은 경우들을 제거한다.

// 그리드의 가장자리에 땅이 있는 경우 해당 타일과 연결된 땅은 물에 둘러쌓여있지 않게되므로
// 가장자리를 우선 탐색하여 연결된 모든 땅 타일을 물 타일로 변경
for(int i = 0; i < n; i++){
    // 가장 윗줄 탐색
    dfs(grid, 0, i, false);
    // 가장 아랫줄 탐색
    dfs(grid, m - 1, i, false);
}
for(int i = 1; i < m - 1; i++){
    // 가장 왼쪽줄 탐색
    dfs(grid, i, 0, false);
    // 가장 오른쪽줄 탐색
    dfs(grid, i, n - 1, false);
}

 

그 후 남아있는 안쪽 셀을 대상으로 탐색을 하게 되면 이때 남아있는 땅 타일들은 모두 바다로 둘러 쌓여있는 타일들이므로 isEnclosed를 true로 탐색하며 땅타일들에 대한 개수를 탐색한다.

// 나머지 안쪽 셀들을 탐색
for(int i = 1; i < m - 1; i++){
    for(int j = 1; j < n - 1; j++){
        dfs(grid, i, j, true);
    }
}

 

탐색이 종료된 후 구해진 정답을 return한다.

return answer;

---

최종 코드

class Solution {
    int answer = 0;

    public int numEnclaves(int[][] grid) {
        // 그리드 행 개수
        int m = grid.length;
        // 그리드 열 개수
        int n = grid[0].length;

        // 그리드의 가장자리에 땅이 있는 경우 해당 타일과 연결된 땅은 물에 둘러쌓여있지 않게되므로
        // 가장자리를 우선 탐색하여 연결된 모든 땅 타일을 물 타일로 변경
        for(int i = 0; i < n; i++){
            // 가장 윗줄 탐색
            dfs(grid, 0, i, false);
            // 가장 아랫줄 탐색
            dfs(grid, m - 1, i, false);
        }
        for(int i = 1; i < m - 1; i++){
            // 가장 왼쪽줄 탐색
            dfs(grid, i, 0, false);
            // 가장 오른쪽줄 탐색
            dfs(grid, i, n - 1, false);
        }
        // 나머지 안쪽 셀들을 탐색
        for(int i = 1; i < m - 1; i++){
            for(int j = 1; j < n - 1; j++){
                dfs(grid, i, j, true);
            }
        }

        return answer;
    }

    /**
     * @param grid  탐색 대상 그리드
     * @param row   현재 탐색중인 행의 인덱스
     * @param col   현재 탐색중인 열의 인덱스
     * @param inEnclosed 현재 탐색중인 타일이 물로 쌓여있는지 여부
     * @return
     */
    public void dfs(int[][] grid, int row, int col, boolean isEnclosed){
        // 좌표가 그리드를 벗어나는 경우 탐색 종료
        if(row < 0 || col < 0 || row >= grid.length || col >= grid[0].length) return;
        // 방문한 타일이 땅(1)인 경우 물(0)로 변경
        // 물로 둘러 쌓여있는 땅 타일인 경우 정답 카운트 증가
        // 상하좌우 타일 탐색하며 모든 인접한 땅타일을 물로 변경
        if(grid[row][col] == 1){
            grid[row][col] = 0;
            if(isEnclosed) answer++;
            dfs(grid, row, col+1, isEnclosed);
            dfs(grid, row, col-1, isEnclosed);
            dfs(grid, row+1, col, isEnclosed);
            dfs(grid, row-1, col, isEnclosed);
        }
    }
}

---