솔루션: 섬의 최대 면적

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #695(중간): 섬의 최대 면적

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

예:

Example 1:
Input:	grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output:	6
Explanation:	The answer is not 11, because the island must be connected 4-directionally.
Visual:

Example 2:
Input:	grid = [[0,0,0,0,0,0,0,0]]
Output:	0

제약:

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

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

따라서 그리드를 통해 간단한 반복을 사용하고 섬을 찾을 수 있습니다. 섬을 찾으면 재귀 도우미 함수(trav)를 사용하여 연결된 모든 토지 조각을 합산하고 섬의 총 토지 질량을 반환할 수 있습니다.

섬을 횡단할 때 같은 땅을 두 번 "찾는"것을 방지하기 위해 1을 0으로 바꿀 수 있습니다. 우리는 또한 지금까지 발견된 가장 큰 섬(ans)을 추적할 수 있으며 그리드를 완전히 통과한 후 ans를 반환할 수 있습니다.

시간 복잡도: O(N * M) 여기서 N과 M은 그리드 측면의 길이입니다

.

공간 복잡도: O(L) 여기서 L은 최대 재귀 스택을 나타내는 가장 큰 섬의 크기입니다.

또는 입력

을 수정하지 않기 위해 N * M 행렬을 만드는 경우 O(N * M + L)

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var maxAreaOfIsland = function(grid) {
    let ans = 0, n = grid.length, m = grid[0].length
    const trav = (i, j) => {
        if (i < 0 || j < 0 || i >= n || j >= m || !grid[i][j]) return 0
        grid[i][j] = 0
        return 1 + trav(i-1, j) + trav(i, j-1) + trav(i+1, j) + trav(i, j+1)
    }
    for (let i = 0; i < n; i++) 
        for (let j = 0; j < m; j++)
            if (grid[i][j]) ans = Math.max(ans, trav(i, j))
    return ans
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans, n, m = 0, len(grid), len(grid[0])
        def trav(i: int, j: int) -> int:
            if i < 0 or j < 0 or i >= n or j >= m or grid[i][j] == 0: return 0
            grid[i][j] = 0
            return 1 + trav(i-1, j) + trav(i, j-1) + trav(i+1, j) + trav(i, j+1)
        for i, j in product(range(n), range(m)):
            if grid[i][j]: ans = max(ans, trav(i, j))
        return ans

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    private int n, m;
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        n = grid.length;
        m = grid[0].length;
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < m; j++)
                if (grid[i][j] > 0) ans = Math.max(ans, trav(i, j, grid));
        return ans;
    }
    private int trav(int i, int j, int[][] grid) {
        if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] < 1) return 0;
        grid[i][j] = 0;
        return 1 + trav(i-1, j, grid) + trav(i, j-1, grid) + trav(i+1, j, grid) + trav(i, j+1, grid);
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < m; j++)
                if (grid[i][j]) ans = max(ans, trav(i, j, grid));
        return ans;
    }
private:
    int n, m;
    int trav(int i, int j, vector<vector<int>>& grid) {
        if (i < 0 || j < 0 || i >= n || j >= m || !grid[i][j]) return 0;
        grid[i][j] = 0;
        return 1 + trav(i-1, j, grid) + trav(i, j-1, grid) + trav(i+1, j, grid) + trav(i, j+1, grid);
    }
};