C++로 지형 계곡 사이에 고이는 빗물의 양을 구하는 프로그램

2차원 행렬이 하나 주어지고, 행렬의 각 원소는 지형의 높이를 나타낸다고 가정해 보겠습니다. 비가 내려서 계곡의 모든 움푹 들어간 공간이 물로 차오르는 상황을 상상할 수 있습니다.

이때 우리가 구해야 할 것은 계곡 사이에 고이게 되는 빗물의 총량입니다.

예를 들어 입력이 다음과 같다면,

출력은 3이 됩니다. 높이가 4와 5인 칸 사이에 물 3단위를 담을 수 있기 때문입니다.

문제 해결 접근 방법

이 문제는 행렬의 바깥쪽 경계부터 시작해 안쪽으로 탐색을 넓혀가는 방식으로 해결할 수 있습니다. 경계에 있는 칸은 물이 밖으로 흘러나갈 수 있는 출구 역할을 하므로, 탐색 과정에서 마주치는 칸의 높이가 지금까지 확인한 최대 경계 높이보다 낮다면 그 차이만큼 물이 고이게 됩니다. 이를 효율적으로 처리하기 위해 높이를 기준으로 정렬되는 우선순위 큐를 활용합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다 −

• x 좌표, y 좌표, 높이 h를 포함하는 구조체 Data를 정의합니다.

• 높이 값을 기준으로 정렬된 항목을 저장하는 우선순위 큐 pq를 정의합니다.

• n := h의 크기

• n이 0이면 0을 반환합니다.

• m := h[0]의 크기

• 좌표 쌍(pair)을 저장하는 집합 visited를 정의합니다.

• i := 0으로 초기화하고, i < n인 동안 i를 1씩 증가시키며 다음을 반복합니다 −

  • Data(h[i, 0], i, 0)를 pq에 삽입하고, {i, 0}을 visited에 삽입합니다.

  • Data(h[i, m - 1], i, m - 1)를 pq에 삽입하고, {i, m - 1}을 visited에 삽입합니다.

• i := 1로 초기화하고, i < m - 1인 동안 i를 1씩 증가시키며 다음을 반복합니다 −

  • Data(h[0, i], 0, i)를 pq에 삽입하고, {0, i}을 visited에 삽입합니다.

  • Data(h[n - 1, i], n - 1, i)를 pq에 삽입하고, {n - 1, i}을 visited에 삽입합니다.

• ret := 0, maxVal := 0으로 초기화합니다.

• pq가 비어 있지 않은 동안 다음을 반복합니다 −

  • temp = pq의 최상위 원소를 꺼내고, pq에서 해당 원소를 제거합니다.

  • maxVal := temp의 높이와 maxVal 중 더 큰 값

  • x := temp의 x 좌표, y := temp의 y 좌표

  • i := 0으로 초기화하고, i < 4인 동안 i를 1씩 증가시키며 다음을 반복합니다 −

    • nx := x + dir[i, 0]

    • ny := y + dir[i, 1]

    • nx >= 0이고 ny >= 0이고 nx < n이고 ny < m이며 {nx, ny}를 아직 방문하지 않았다면 −

      • val := h[nx, ny]

      • val < maxVal이라면 −

        • ret := ret + maxVal - val

        • val := maxVal

      • Data(val, nx, ny)를 pq에 삽입하고, {nx, ny}을 visited에 삽입합니다.

• ret을 반환합니다.

예시

더 잘 이해하기 위해 다음 구현을 살펴보겠습니다 −

#include <bits/stdc++.h>
using namespace std;
struct Data {
    int x, y;
    int h;
    Data(int a, int b, int c) {
        h = a;
        x = b;
        y = c;
    }
};
struct Comparator {
    bool operator()(Data a, Data b) {
        return !(a.h < b.h);
    }
};
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
    public:
    int solve(vector<vector<int>>& h) {
        priority_queue<Data, vector<Data>, Comparator> pq;
        int n = h.size();
        if (!n)
            return 0;
        int m = h[0].size();
        set<pair<int, int>> visited;
        for (int i = 0; i < n; i++) {
            pq.push(Data(h[i][0], i, 0));
            visited.insert({i, 0});
            pq.push(Data(h[i][m - 1], i, m - 1));
            visited.insert({i, m - 1});
        }
        for (int i = 1; i < m - 1; i++) {
            pq.push(Data(h[0][i], 0, i));
            visited.insert({0, i});
            pq.push(Data(h[n - 1][i], n - 1, i));
            visited.insert({n - 1, i});
        }
        int ret = 0;
        int maxVal = 0;
        while (!pq.empty()) {
            Data temp = pq.top();
            pq.pop();
            maxVal = max(temp.h, maxVal);
            int x = temp.x;
            int y = temp.y;
            int nx, ny;
            for (int i = 0; i < 4; i++) {
                nx = x + dir[i][0];
                ny = y + dir[i][1];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited.count({nx, ny})) {
                    int val = h[nx][ny];
                    if (val < maxVal) {
                        ret += maxVal - val;
                        val = maxVal;
                    }
                    pq.push(Data(val, nx, ny));
                    visited.insert({nx, ny});
                }
            }
        }
        return ret;
    }
};
int solve(vector<vector<int>>& matrix) {
    return (new Solution())->solve(matrix);
}
int main(){
    vector<vector<int>> v = {
        {6, 6, 6, 8},
        {6, 4, 5, 8},
        {6, 6, 6, 6}
    };
    cout << solve(v);
}

입력

{
    {6, 6, 6, 8},
    {6, 4, 5, 8},
    {6, 6, 6, 6}
};

출력

3