Leetcode 695. Max Area of Island with Python

문제

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.

m*n 으로 이루어진 2차원 배열이 주어진다.
배열에서 1은 육지를 의미하고 0은 바다를 의미한다.
육지는 상하좌우로 이어져 하나의 큰 섬을 이룰수 있다.
가장 큰 섬의 크기를 리턴하시오.

예시

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: 가장 큰 섬은 주황색으로 칠해진 섬으로, 총 6의 너비를 가진다. 
             아래의 섬과는 상하좌우로 연결되어 있지 않기 때문에 같은 섬은 아니다.
             

풀이

dfs를 이용해 섬을 채워 나가며

새로운 섬을 마주했을때 그 섬의 너비를 구하는 함수를 만들어 사용한다.

그 함수의 값이 최대가 되는 것을 저장하여 리턴한다.

 def search(grid: List[List[int]], vert: int, hori: int, vertSize: int, horiSize: int):
    mv = [-1, 0, 1, 0]
    mh = [0, -1, 0, 1]
    grid[vert][hori] = 2

    count = 1
    for i in range(4):
        tv = vert + mv[i]
        th = hori + mh[i]
        if tv < 0 or tv >= vertSize or th < 0 or th >= horiSize or grid[tv][th] != 1: continue
        count += search(grid, tv, th, vertSize, horiSize)

    return count


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    count = max(count, search(grid, i, j, len(grid), len(grid[0])))
        return count