[LeetCode]Max Area of Island

https://leetcode.com/problems/max-area-of-island/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 그리드에서 가장 큰 섬의 크기를 구하는 문제입니다.

 

처음 시도한 답안

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

        dx = [1,0,-1,0]
        dy = [0,1,0,-1]

        answer = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    queue = [(i,j)]
                    grid[i][j] = 0
                    count = 1

                    while queue:
                        i, j = queue.pop(0)

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

                            if x < 0 or y < 0 or x >= m or y >= n or grid[x][y] == 0:
                                continue

                            queue.append((x,y))
                            grid[x][y] = 0
                            count += 1

                    answer = max(answer, count)

        return answer

접근 방법

1. 이중 포문을 순회하면서 BFS 방식으로 섬을 순회합니다.
2. 만약 등장한 지점이 1이라면 (섬이라면)
   1. 등장한 지점을 큐에 넣고 방문 처리를 합니다.
   2. count(섬의 크기)를 1로 설정한 후 이어진 섬들을 BFS로 방문합니다.
   3. 큐에서 해당 지점을 뺀 후 상하좌우로 방문이 가능한지 확인합니다.
   4. 방문이 가능하다면 해당 지점을 큐에 넣은 후 방문 처리를 합니다.
   5. 이 때 방문이 가능하기 때문에 섬의 크기를 1 증가합니다.
   6. 가장 큰 섬의 크기를 업데이트하기 위해 answer와 count중 큰 값을 answer로 정합니다.

이어져 있는 섬을 BFS로 탐색하고 섬의 최대 크기를 저장하면서 구하면 되는 문제입니다.