2468번: 안전 영역

https://www.acmicpc.net/problem/2468


$O(n^2lgn)$

처음에 모든 지점이 물에 잠겨있고 높이가 큰 지점부터 드러난다고 생각하자.
현재 섬 개수가 c라고 하면 어떤 지점 x가 드러날때 추가로 드러난 섬의 개수는 1-(x 상하좌우에 이미 드러난 섬개수)이다.
c가 가장 클 때가 답이다.
유니온 파인드 자료구조를 이용해 여러 지점들을 하나의 섬으로 합칠 수 있을 것이다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 100, fx[] = { 1,-1,0,0 }, fy[] = { 0,0,1,-1 };
int n, par[MXN*MXN], r, c, ck[MXN][MXN];
int f(int x) { return x - par[x] ? par[x] = f(par[x]) : x; }
pair<int, int> p[MXN*MXN];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n*n; i++) scanf("%d", &p[i].first), p[i].second = par[i] = i;
    sort(p, p + n*n);
    for (int i = n*n - 1; i >= 0; i--) {
        c++;
        ck[p[i].second / n][p[i].second%n] = 1;
        for (int j = 0; j < 4; j++) {
            int tx = p[i].second / n + fx[j], ty = p[i].second%n + fy[j], t = tx*n + ty;
            if (tx >= 0 && ty >= 0 && tx < n && ty < n && ck[tx][ty] && f(t) != f(p[i].second)) par[f(t)] = f(p[i].second), c--;
        }
        if (!i || p[i - 1].first != p[i].first) r = r>c ? r : c;
    }
    printf("%d", r);
    return 0;
}