leetcode 827 - Making A Large Island

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

풀이

먼저 모든 island를 flood fill 하면서 구분 짓고 크기를 센다. 0은 경계선이고 1은 island라는 의미를 가지기 때문에 아래 코드에서는 island id는 2부터 증가하는 숫자로 구분 지었다. 

 

island를 구분 짓고 크기를 세었으면 모든 0인 부분에 대해서 1로 바꿔보고 이웃한 island의 크기를 합해본다. 4방향 이웃의 크기를 더할 때 같은 island인 경우 중복해서 더하면 안 되기 때문에 먼저 island id로 중복을 제거한다.

 

모든 맵을 순회 하면서 flood fill을 한번 하기 때문에 시간 복잡도는 $O(n^2)$ 이다.

 

 

코드

class Solution {
public:
    vector<vector<int>> dir{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int largestIsland(vector<vector<int>>& grid) {
        map<int, int> islandCount;
        
        int islandId = 2;
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[0].size(); j++) {
                if(grid[i][j] == 0) continue;
                islandCount[islandId++] = fillAndCount(grid, i, j, islandId);
            }
        }
        
        int ans = 0;
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[0].size(); j++) {
                set<int> neighbor = { grid[i][j] };
                for(int k = 0; k < 4; k++) {
                    if(validateSize(i + dir[k][0], j + dir[k][1], grid.size(), grid[0].size()))
                        neighbor.insert(grid[i + dir[k][0]][j + dir[k][1]]);
                }

                ans = max(ans, (grid[i][j] == 0) + accumulate(neighbor.begin(), neighbor.end(), 0, [&islandCount](int sum, int id) { return sum + islandCount[id]; }));
            }
        }
        
        return ans;
    }
    
    int fillAndCount(vector<vector<int>>& grid, int row, int col, int fill) {
        if(!validateSize(row, col, grid.size(), grid[0].size())) return 0;
        if(grid[row][col] != 1) return 0;
        
        grid[row][col] = fill;
        int size = 1;
        for(int i = 0; i < 4; i++) {
            size += fillAndCount(grid, row + dir[i][0], col + dir[i][1], fill);
        }
        
        return size;
    }
    
    bool validateSize(int row, int col, int maxRow, int maxCol) {
        return row >= 0 && row < maxRow && col >= 0 && col < maxCol;
    }
};