[알고리즘] Max Area of Island

포인트

• 주어진 지도에서 섬들이 여러 개가 있다. 이 중에 제일 큰 섬의 크기를 구하라. 가 쟁점입니다.
• 그러면 섬의 크기는 어떻게 구할까요?
  섬의 크기는 BFS 알고리즘을 이용하여 1 인 지점을 순회를 하면서 방문 배열의 표시를 해주면서 섬의 크기를 늘려가는 방식으로 구해줍니다. 
• 어떻게 보면 너비 우선 탐색에 제일 기본형일고 할 수 있습니다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

class Solution:
    def bfs(self, row: int, col: int, visited: list, n: int, m: int, grid: list) -> int:
        q = deque()
        q.append([row, col])
        visited[row][col] = 1
        cnt = 1
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]

        while q:
            x, y = q.popleft()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if not (0 <= nx < n and 0 <= ny < m):
                    continue
                if grid[nx][ny] == 1 and visited[nx][ny] == 0:
                    cnt += 1
                    visited[nx][ny] = 1
                    q.append([nx, ny])
        return cnt

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])

        visited = [[0] * m for _ in range(n)]
        answer = 0
        for row in range(n):
            for col in range(m):
                if visited[row][col] == 0 and grid[row][col] == 1:
                    result = self.bfs(row, col, visited, n, m, grid)
                    answer = max(answer, result)
        return answer