LeetCode 솔루션 분류
[7/15] 695. Max Area of Island
본문
Medium
7297167Add to ListShareYou 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.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]] Output: 0
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j]
is either0
or1
.
Accepted
559,962
Submissions
786,202
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
import collections
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
visited = set()
ROW, COL = len(grid), len(grid[0])
max_area = 0
directions = [(1,0),(0,1),(-1,0),(0,-1)]
def bfs(r, c):
area = 0
queue = collections.deque([(r,c)])
visited.add((r,c))
area = 0
while queue:
area += len(queue)
for i in range(len(queue)):
row, col = queue.popleft()
for r_dir, c_dir in directions:
nr, nc = row+r_dir, col+c_dir
if 0<=nr<ROW and 0<=nc<COL and (nr,nc) not in visited and grid[nr][nc]:
visited.add((nr,nc))
queue.append((nr,nc))
return area
for row in range(ROW):
for col in range(COL):
if grid[row][col] and (row,col) not in visited:
max_area = max(max_area, bfs(row,col))
return max_area