LeetCode 솔루션

[7/15] 695. Max Area of Island

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.07.15 21:23

3,548 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

Medium

7297167Add to ListShare

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.

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 either 0 or 1.

Accepted

559,962

Submissions

786,202

#Amazon, #Facebook, #Microsoft, #Google, #Qualtrics, #Apple, #Bloomberg, #LinkedIn, #Dropbox, #DoorDash, #Walmart Global Tech, #Palantir Technologies

링크

https://leetcode.com/problems/max-area-of-island/ 1593 회 연결

익명
작성일 2022.07.15 21:25

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

[code=Python 3]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[/code]