2276번: 물 채우기

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


$O(nm\lg (nm))$

수면이 점점 올라가 잠긴다고 생각하자.
잠기는 구역이 새로 생길때 (수면의 높이)-(잠기는 구역 높이) 합을 누적하면 답을 구할 수 있다.
답을 빠르기 구하기 위해 우선순위 큐 pq를 사용하자.
pq는 (잠기기 시작하는 지점 위치, 높이 h) 정보를 가지고 있고 작은 높이의 원소가 top이 된다.
top의 지점에서 시작해서 아직까지 잠기지 않은 지점들 중 h보다 작거나 같은 지점들을  모두 체크해주고 h-(잠기는 구역 높이)를 누적한다.
새로 체크된 주변 지점들 중 체크되지 않은 지점들을 pq에 넣고 이를 반복한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 1,0,-1,0 }, fy[] = { 0,1,0,-1 };
int n, m, ck[300][300], h[300][300], r;
struct st {
    int x, y;
    bool operator<(st i) const {
        return h[x][y] > h[i.x][i.y];
    }
};
priority_queue<st> pq;
void dfs(int x, int y, int z) {
    for (int i = 0; i < 4; i++) {
        int tx = x + fx[i], ty = y + fy[i];
        if (tx >= 0 && ty >= 0 && tx < m&&ty < n&&!ck[tx][ty]) {
            ck[tx][ty] = 1;
            if (h[tx][ty] > z) pq.push({ tx,ty });
            else {
                r += z - h[tx][ty];
                dfs(tx, ty, z);
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", h[i] + j);
            if (i == 0 || j == 0 || i == m - 1 || j == n - 1) pq.push({ i,j }), ck[i][j] = 1;
        }
    }
    while (!pq.empty()) {
        st t = pq.top();
        pq.pop();
        dfs(t.x, t.y, h[t.x][t.y]);
    }
    printf("%d", r);
    return 0;
}