[LeetCode] 695. Max Area of Island

https://leetcode.com/problems/max-area-of-island/description/

Max Area of Island - LeetCode

695. Max Area of Island - Medium

 

0과 1로 땅인지 물인지 나타내는 지도가 있다.

이 때, 가장 넓은 섬의 면적이 몇인지 구하는 문제다.

 

dfs 로 풀어도 되지만 조금 다른 방법으로 생각을 해 union-find로 문제를 풀었다.

가장 처음 만나는 땅을 parent로 생각하고, 순차적으로 union-find를 해줬다.

parent grid에는 섬의 면적을 저장하고,

다른 grid에는 parent를 나타내는 수를 저장했다.

parent를 나타내는 수로 -i * 1000 - j*10 -1 을 사용했다. (최대 (50,50) 이므로 100만 곱해도 되지만 (0,0)일 경우를 생각해 10을 더 곱하고 -1을 해주자)

class Solution {
public:
    pair<int, int> f(vector<vector<int>>& g, pair<int, int> p1) {
        if (g[p1.first][p1.second] > 0) return p1;
        return f(g, {-g[p1.first][p1.second] / 1000, -(g[p1.first][p1.second] % 1000)/10});
    }
    int u(vector<vector<int>>& g, pair<int, int> p1, pair<int, int> p2) {
        pair<int, int> pp1 = f(g, p1), pp2 = f(g, p2);
        if (!(pp1.first == pp2.first && pp1.second == pp2.second)) {
            g[pp1.first][pp1.second] += g[pp2.first][pp2.second];
            g[pp2.first][pp2.second] = -pp1.first * 1000 - pp1.second * 10 - 1;
        }
        return g[pp1.first][pp1.second];
    }
    int maxAreaOfIsland(vector<vector<int>>& g) {
        int r = 0;
        for (int i=0; i<g.size(); i++) {
            for (int j=0; j<g[i].size(); j++) {
                if (g[i][j]) {
                    r = max(r, g[i][j]);
                    if (i && g[i-1][j]) r = max(r, u(g, {i-1, j}, {i,j}));
                    if (j && g[i][j-1]) r = max(r, u(g, {i, j-1}, {i,j}));
                }
            }
        }
        return r;
    }
};