[LeetCode] 695. Max Area of Island

[LeetCode] Max Area of Island

이 문제는 dfs 를 활용해서 풀 수 있는 문제이다.

dfs 는 depth first search 의 약자로서, 그래프 탐색 알고리즘의 한 종류이다.

이름에서 알 수 있듯이 노드에서 연결된 노드가 있으면 계속 연결된 부분을 통해 이동하면서 그래프를 탐색한다.

dfs 는 운이 좋을 경우 해를 빠르게 구할 수 있지만, 항상 최적의 해를 보장하지는 않는다.

또한 dfs 는 스택 자료구조를 사용하며 구현할 수 있다. (재귀의 동작이 스택과 똑같음)

해가 없는 경로에 깊게 빠질 수 있다. 따라서 예외처리를 잘 해주어야한다.

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        
        def dfs(r,c):
            nonlocal count
            if (r < 0 or r >= n or c < 0 or c >= m or grid[r][c] == 0):
                return ;
            
            if (grid[r][c] == 1):
                count += 1
                grid[r][c] = 0;
            
            dfs(r+1,c)
            dfs(r-1,c)
            dfs(r,c+1)
            dfs(r,c-1)
        
        ret = 0;
        
        for i in range(n):
            for k in range(m):
                if (grid[i][k] == 1):
                    count = 0;
                    dfs(i,k)
                    ret = max(count, ret);
        return ret