[LeetCode] 695 | Max Area of Island | Python

---

문제 링크: https://leetcode.com/problems/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.

---

조건

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

---

내 풀이

grid[y][x]가 1인 곳에서 dfs를 해서 영역을 잰다.

bfs로 풀어도 된다.

---

코드

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:    return 0
        N, M = len(grid), len(grid[0])
        visited = [[0]*M for _ in range(N)]
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        ans = 0
        
        def dfs(x, y):
            visited[y][x] = 1

            for t in range(4):
                newX, newY = x+dx[t], y+dy[t]

                if 0<=newX<M and 0<=newY<N and not visited[newY][newX] and grid[newY][newX]:
                    self.count += 1
                    dfs(newX, newY)
        
        for y in range(N):
            for x in range(M):
                if not visited[y][x] and grid[y][x]:
                    self.count = 1
                    dfs(x, y)
                    ans = max(ans, self.count)
                    self.count = 0
                    
        return ans