[medium] 695. Max Area of Island

문제

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

---

풀이방법

자주 보이는 BFS 문제 유형이다.

grid 전체를 탐색하는데 이미 방문한 곳은 체크하면서 중복 탐색하지 않도록 해야한다. (grid 값이 0인 부분은 탐색할 필요없다)

그리고 탐색하는 과정에서 1이 이어져있는 부분의 넓이를 계산하며 최대 넓이를 저장해두었다가, 전체 탐색이 끝나면 최대 넓이를 리턴한다.

그래서 시간복잡도는 O(M*N), 공간복잡도도 O(M*N)

반응형

---

코드

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        M = len(grid)
        N = len(grid[0])
        visit = [[False]*N for i in range(M)]
        direction = [[-1,0],[1,0],[0,-1],[0,1]]
        result = 0

        def bfs(m,n):
            area = 0
            queue = []
            queue.append((m,n))
            while queue:
                m,n = queue.pop(0)
                
                if visit[m][n]:
                    continue
                    
                visit[m][n] = True
                area += 1
                
                for dm,dn in direction:
                    newm = m + dm
                    newn = n + dn
                    if newm>=0 and newm<M and newn>=0 and newn<N and grid[newm][newn]==1 and visit[newm][newn]==False:
                        queue.append((newm,newn))
            return area

        for m in range(M):
            for n in range(N):
                if visit[m][n] or grid[m][n]==0:
                    continue
                result = max(bfs(m,n), result)
                
        return result