8068 Water

지형이 주어질 때 물이 최대 얼마나 고이는지 물어보는 문제다. 가장자리에는 고이지 않는다.

가장자리부터 물이 차오를 때 언제 내부가 잠기는지를 구하면 된다.

새로운 배열을 만들고 가장자리를 priority_queue에 입력해 준 후 x,y까지 오면서 들렀던 타일 중 최대값으로 새로운 배열을 채운다.

그 후 원래 배열값과의 차이를 다 더하면 그게 답이다.

testcase도 찾아보면 있으니 직접 디버깅 해 보면 어떤방식으로 돌아가는지 쉽게 알 수 있다.

<코드>

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
 
typedef pair<int, int> pii;
 
int n, m, a[101][101], dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 }, ans, d[101][101];
priority_queue<pair<int, pii>> q;
 
int main() {
    memset(d, -1, sizeof(d));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) 
        scanf("%d", &a[i][j]);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (!i || !j || i == n - 1 || j == m - 1) 
        q.push({ -a[i][j], {i,j} });
    while (q.size()) {
        int c = -q.top().first;
        int x = q.top().second.first;
        int y = q.top().second.second;
        q.pop();
        if (d[x][y] != -1) continue;
        d[x][y] = c;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            q.push({ -max(c,a[nx][ny]),{nx,ny} });
        }
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) 
        ans += d[i][j] - a[i][j];
    printf("%d\n", ans);
    return 0;
}