[LeetCode] 827. Making A Large Island

https://leetcode.com/problems/making-a-large-island/description/

leetcode - Making A Large Island

문제 유형: BFS, 유니온-파인드, 그래프

문제 난이도: Hard

 

문제

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

 

n x n의 바이너리 행렬 grid가 주어진다. 최대 하나의 0을 1로 바꿀 수 있다.

연산을 적용한 후에 가장 큰 섬의크기를 구하시오. 1로 연결된 그룹이 섬입니다.

 

풀이

분리 집합으로 풀 수 있다고 하지만.. 여기서는 bfs로 한다. 어차피 비슷하다.

bfs를 돌려서 각 연결 컴포넌트의 크기를 저장해두고, grid에는 컴포넌트의 id를 새겨놓는다.

이후, 0인 칸에서 인접한 연결 컴포넌트들의 크기들을 더하고 +1(자신을 메꿈)한 값을 최대값으로 갱신시도한다.

또는 연산을 적용하지 않을 수 있어서 최대값은 이미 존재하는 가장 큰 섬일 수도 있다.

 

최종적으로 가장 큰 값을 반환한다.

 

코드

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 largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> groupsize = {0, 0};
        int k = 2;
        int maxGroupSize = 0;

        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(grid[i][j] == 1) {
                    int count = 1;
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    grid[i][j] = k;
                    while(!q.empty()) {
                        auto curr = q.front();
                        int x = curr.first;
                        int y = curr.second;
                        q.pop();

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

                            if(nx < 0 || ny < 0 || nx >= n || ny >= n || grid[nx][ny] == 0) continue;
                            if(grid[nx][ny] == 1) {
                                q.push({nx, ny});
                                grid[nx][ny] = k;
                                count++;
                            }
                        }
                    }
                    groupsize.push_back(count);
                    maxGroupSize = max(maxGroupSize, count);
                    k++;
                }
            }
        }
        
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(grid[i][j] == 0) {
                    set<int> adjComps;
                    for(int l = 0; l < 4; ++l) {
                        int nx = i + dx[l];
                        int ny = j + dy[l];
                        if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
                            adjComps.insert(grid[nx][ny]);
                        }
                    }
                    int sum = 1;
                    for(const auto &comp : adjComps) {
                        sum += groupsize[comp];
                    }
                    maxGroupSize = max(maxGroupSize, sum);
                }
            }
        }

        return maxGroupSize;
    }
};