[LeetCode] 2658번: Maximum Number of Fish in a Grid

Hint

1. 물고기가 있는 곳에서 DFS 알고리즘을 이용해 물고기 수 세기
2. DFS 시작지점을 찾았다면 연결된 모든 물고기 있는 곳에서 물고기 수 더하기
3. 물고기 있는 곳을 이미 방문했는지 확인하는 리스트가 필요함 (중복으로 더하기 않게)

 

LeetCode 2658번: Maximum Number of Fish in a Grid (풀어보기)

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        # 낚시가 이미 된 부분 표시해주는 세트
        fished = set()
        
        def fishing(r, c):
            # 아래 3가지가 다 통과하지 못하면 물고기가 없으므로 0을 반환함
            if not (0 <= r < len(grid) and 0 <= c < len(grid[0])    # r, c가 grid 안에 있는 값이어야함
                   and (r, c) not in fished     # 낚시 이미 한 구역이 아닌지 확인
                   and grid[r][c]):             # r, c에 있는 grid 값이 0이 아닌 물고기가 있는 물이어야함
                return 0
            
            # 낚시 끝난 구역으로 표시함
            fished.add((r,c))
            
            # 현재 위치에서 사방으로 다 확인하고 물고기 수를 더해줘야함
            return (grid[r][c] + fishing(r+1, c) + fishing(r, c+1) + fishing(r, c-1) + fishing(r-1, c))
        
        # dfs 방식으로 물고기 수 다 센 후 가장 물고기가 많았던 수를 반환
        return max(fishing(r, c) for r in range(len(grid)) for c in range(len(grid[0])))