695. Max Area of Island

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:

Constraints:

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

---

# https://leetcode.com/problems/max-area-of-island/description/

'''
1. 아이디어 :
    dfs 로 풀 수 있다.
2. 시간복잡도 :
    O(4mn)
    4 방향 탐색 * grid 크기
3. 자료구조 :

'''


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        cmax = 0

        def dfs(x,y):
            if x<0 or y<0 or x==len(grid) or y==len(grid[0]) or grid[x][y] != 1:
                return 0

            grid[x][y]=0
            return 1 + dfs(x+1,y) + dfs(x-1,y) + dfs(x,y+1) + dfs(x,y-1)

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]!=0:
                    cmax = max(cmax, dfs(i,j))

        return cmax