[BOJ] 백준 15972 물탱크

출처: https://www.acmicpc.net/problem/15972

 Input 

2 3 5

1 -1 -1

3 2 -1

4 -1 2

-1 -1 4 3

-1 -1 -1 -1

 

 Output 

17

우선 순위 큐를 이용해서 물 높이가 낮은 칸 부터 처리합니다.

가장 외벽들로 부터 BFS 탐색을 시작합니다. (높이가 낮은것부터 처리하는 우선순위 큐 이용)

(외벽 바깥에 구멍이 존재할 때, 물이 마지막 빠져나가는 곳이기 때문입니다.)

위와 같이 가장자리 외벽에 높이 2, 높이 3 구멍이 있다면 더 작은 높이로 시작

 

각 격자마다 구멍이 날 수 있는 곳은 최대 4개 입니다.

 위(0), 오른쪽(1), 아래(2), 왼쪽(3)

 

Q) BFS 탐색하면서 물의 높이는 어떻게 조정될까?

구멍으로 이어진(next) 칸의 물 높이는 단순하게 생각했을 때는 구멍의 높이에 해당될 것 같지만

구멍으로 이어진 칸(cur)의 물 높이가 구멍 높이보다 크다는 것은

해당 구멍이 높이에 영향을 주지 않는 것을 의미합니다.

 구멍에 맞춰서 높이를 조정합니다.

 구멍의 높이와 별개로 인접한 물탱크의 높이와 맞춰집니다.

- 먼저, 구멍의 높이와 접하고 있는 물탱크에 존재하는 물 높이 중 최솟값을 구합니다.

min(hole[cur.x][cur.y][i], tank[nextX][nextY])

- 위에서 구한 수치와 현재 물 높이 중 더 큰 값이 구멍과 인접한 물탱크에서 설정되는 높이입니다.

max(min(hole[cur.x][cur.y][i], tank[nextX][nextY]), tank[cur.x][cur.y]);

 

위와 같은 물높이 갱신을 (BFS 탐색하며) 최대 4개 방향에서 더 낮은 높이의 구멍을 우선적으로 처리합니다.

 

---

#include <stdio.h>
inline int max(int A, int B) { return A > B ? A : B; }
inline int min(int A, int B) { return A < B ? A : B; }
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int N, M, H, ans, z;
int hole[1003][1003][4], tank[1003][1003];
struct Water {
    int height, x, y;
};
bool comp(Water A, Water B) { return A.height < B.height; }
void swap(Water& A, Water& B) { Water t = A; A = B; B = t; }
struct PriorityQueue {
    Water heap[1000 * 1000];
    int heapSize;
    bool(*cmp)(Water, Water);
    void init() {
        heapSize = 0;
        cmp = comp;
    }
    Water top() { return heap[1]; }
    int size() { return heapSize; }
    void push(Water data) {
        heap[++heapSize] = data;
        int c = heapSize;
        for (; c > 1 && cmp(heap[c], heap[c / 2]); c /= 2) {
            swap(heap[c], heap[c / 2]);
        }
    }
    void pop() {
        int p = 1, c = 2;
        swap(heap[1], heap[heapSize--]);
        for (; c <= heapSize; p = c, c *= 2) {
            if (c < heapSize && cmp(heap[c + 1], heap[c])) {
                c++;
            }
            if (!cmp(heap[c], heap[p])) break;
            swap(heap[c], heap[p]);
        }
    }
}pq;
 
// 구멍에 맞는 높이로 설정되는 경우 pq에 push
void tryPush(int x, int y, int h) {
    // 보다 낮은 높이인 경우
    if (tank[x][y] <= h) return;
    
    tank[x][y] = h;
    pq.push({ h, x, y });
}
 
void input() {
    register int i, j;
    scanf("%d %d %d", &N, &M, &H);
    // 상하 구멍 표시
    for (i = 1; i <= N + 1; ++i) {
        for (j = 1; j <= M; ++j) {
            scanf("%d", &z);
            hole[i - 1][j][2] = z;
            hole[i][j][0] = z;
        }
    }
    // 좌우 구멍 표시
    for (i = 1; i <= N; ++i) {
        for (j = 1; j <= M + 1; ++j) {
            scanf("%d", &z);
            hole[i][j - 1][1] = z;
            hole[i][j][3] = z;
        }
    }
    // 구멍이 없다고 생각하며 물을 가득 채웁니다.
    for (i = 1; i <= N; ++i) {
        for (j = 1; j <= M; ++j) {
            tank[i][j] = H;
        }
    }
}
 
void BFS() {
    register int i, j, nextX, nextY, nextHeight;
    Water cur;
    // 우선순위 큐 생성
    pq.init();
    // 바깥쪽에 있는 구멍 높이를 기준으로 설정
    for (i = 0; i <= M + 1; ++i) { // 상, 하
        if (hole[0][i][2] != -1)
            tryPush(1, i, hole[0][i][2]);
        if (hole[N + 1][i][0] != -1)
            tryPush(N, i, hole[N + 1][i][0]);
    }
    for (i = 0; i <= N + 1; ++i) { // 좌, 우
        if (hole[i][0][1] != -1)
            tryPush(i, 1, hole[i][0][1]);
        if (hole[i][M + 1][3] != -1)
            tryPush(i, M, hole[i][M + 1][3]);
    }
    while (pq.size()) {
        cur = pq.top(); pq.pop();
        // 이미 갱신처리된 경우
        if (cur.height != tank[cur.x][cur.y])
            continue;
        for (i = 0; i < 4; i++) {
            // 구멍이 없는 방향인 경우
            if (hole[cur.x][cur.y][i] == -1)
                continue;
            nextX = cur.x + dx[i];
            nextY = cur.y + dy[i];
            // 범위를 벗어나는 경우
            if (nextX < 1 || nextY < 1 || nextX > N || nextY > M)
                continue;
            nextHeight = max(min(hole[cur.x][cur.y][i], tank[nextX][nextY]),  tank[cur.x][cur.y]);
            tryPush(nextX, nextY, nextHeight);
        }
    }
    
    // 물의 총량(부피) 구하기
    for (i = 1; i <= N; i++) {
        for (j = 1; j <= M; j++) {
            ans += tank[i][j];
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    BFS();
    printf("%d\n", ans);
}