[LeetCode] 658. Maximum Number of Fish in a Grid

https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/description/

leetcode - Maximum Number fof Fish in a Grid

문제 유형: bfs/dfs

문제 난이도: 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.

 

2D배열 grid가 주어진다. 0이면 육지고, 0보다 크면 물고기의 수가 들어있는 바다이다.

한 바다만을 먹을 수 있다면, 얻을 수 있는 최대의 물고기수를 구하시오.

 

풀이

컴포넌트의 최대 물고기수를 반환하면 된다.

bfs로 연결 컴포넌트의 물고기수를 구할 수 있음을 알 수 있다.

각 순회마다 최대 물고기수를 업데이트하여 최종 값을 리턴한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        int ans = 0;

        vector<vector<bool>> visited(n, vector<bool>(m, false));

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(!visited[i][j] && grid[i][j] > 0) {
                    int cnt = grid[i][j];
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    visited[i][j] = true;

                    while(!q.empty()) {
                        auto curr = q.front();
                        int x = curr.first;
                        int y = curr.second;
                        q.pop();

                        for(int k = 0; k < 4; ++k) {
                            int nx = x + dx[k];
                            int ny = y + dy[k];

                            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                            if(visited[nx][ny] || grid[nx][ny] == 0) continue;

                            q.push({nx, ny});
                            visited[nx][ny] = true;
                            cnt += grid[nx][ny];
                        }
                    }

                    ans = max(ans, cnt);
                }
            }
        }

        return ans;
    }
};