695. Max Area of Island (Array, Depth-First Search, Breadth-First Search, Union Find, Matrix)

링크 - https://leetcode.com/problems/max-area-of-island/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

DFS, BFS모두 사용 가능하다. 난 여기서 BFS를 사용하였다.

Code

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

        rows = len(grid)
        cols = len(grid[0])

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 1:
                    grid[row][col] = -1
                    area = 0
                    queue = deque()
                    queue.append((row, col))

                    while queue:
                        r, c = queue.popleft()
                        area += 1
                        if r > 0 and grid[r-1][c] == 1:
                            grid[r-1][c] = -1
                            queue.append((r-1, c))
                        if c > 0 and grid[r][c-1] == 1:
                            grid[r][c-1] = -1
                            queue.append((r, c-1))
                        if r < rows-1 and grid[r+1][c] == 1:
                            grid[r+1][c] = -1
                            queue.append((r+1, c))
                        if c < cols-1 and grid[r][c+1] == 1:
                            grid[r][c+1] = -1
                            queue.append((r, c+1))

                    max_area = max(max_area, area)

        return max_area

Complexity

Time Complexity: O(M*N)

Space Complexity: O(M*N)