[LeetCode] 2658. Maximum Number of Fish in a Grid (Python)

 

난이도: Medium

문제 설명

---

You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:

• A land cell if grid[r][c] = 0, or
• A water cell containing grid[r][c] fish, if grid[r][c] > 0.

A fisher can start at any water cell (r, c) and can do the following operations any number of times:

• Catch all the fish at cell (r, c), or
• Move to any adjacent water cell.

Return the maximum number of fish the fisher can catch if he chooses his starting cell optimally, or 0 if no water cell exists.

 

An adjacent cell of the cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) or (r - 1, c) if it exists.

 

문제 예제

---

Example 1:

Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
Output: 7
Explanation: The fisher can start at cell (1,3) and collect 3 fish, then move to cell (2,3) and collect 4 fish.

Example 2:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
Output: 1
Explanation: The fisher can start at cells (0,0) or (3,3) and collect a single fish.

 

제한 사항

---

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• 0 <= grid[i][j] <= 10

 

Solution(솔루션)

---

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

        moves = [[0,1], [0,-1], [1,0], [-1,0]]
        visited = [[False] * m for _ in range(n)]
        answer = 0

        for i in range(n):
            for j in range(m):
                if grid[i][j] != 0:
                    q = deque([])
                    q.append((i,j))
                    visited[i][j] = True

                    fish = 0
                    while q:
                        x, y = q.popleft()
                        fish += grid[x][y]

                        for move in moves:
                            nx = x + move[0]
                            ny = y + move[1]

                            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and grid[nx][ny] != 0:
                                visited[nx][ny] = True
                                q.append((nx, ny))

                    answer = max(answer, fish)
        
        return answer

 

bfs를 통해 문제를 해결했지만, dfs로도 충분히 해결할 수 있을 것 같다.

 

모든 0이 아닌 cell에서 시작하여 상하좌우 움직이며 모을 수 있는 fish의 수를 세었다.

 

센 fish의 수를 answer와 비교해 answer보다 크면 이를 answer에 저장했다.

 

마지막에는 이 answer를 return하여 정답을 맞을 수 있었다.

---

문제: 2658. Maximum Number of Fish in a Grid

 

깃허브: github

algorithmPractice/LeetCode/2764-maximum-number-of-fish-in-a-grid at main · laewonJeong/algorithmPractice