[LeetCode] 407. Trapping Rain Water II

https://leetcode.com/problems/trapping-rain-water-ii/description/

leetcode - Trapping Rain Water II

문제 유형: 우선순위 큐, bfs

문제 난이도: Hard

 

문제

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

 

m x n의 정수 행렬 heightMap이 주어진다. 이는 2D의 높이 지도를 셀단위로 나타내는데, 비가 오고 난 뒤 물이 고이는 물의 총 양을 구하여라.

 

풀이

처음에는 https://riveroverflow.tistory.com/entry/LeetCode-42-Trapping-Rain-Water

[LeetCode] 42. Trapping Rain Water

에서의 문제와 똑같은 접근을 하려고 상하좌우에 대해서 조사했는데, 아니였다.

 

그 다음으로는, 내부 셀(0이나 n-1, m-1이 아닌 셀)에서 가장 높은 위치부터 내려가는 접근을 택했는데, 이 역시 아니였다. 만약 바깥으로 흘러가버리면 안 되기 때문이다.

 

정답은 바깥둘레들부터 최소힙 우선순위 큐에 {높이, 행, 열}을 넣어서 낮은 겉면의 낮은높이들부터 올라가는 식이었다.

즉, 1D배열에서의 케이스의 확장은 맞으나, 단순히 행들과 열들단위로 읽을 게 아니라, 우선순위 큐와 bfs를 이용하여 최대높이의 개념을 '연결 컴포넌트' 단위로 해야 했던 것이다.

 

그래서, 우선순위 큐에서 숫자를 빼서 유효한 범위에 가본적 없는 위치에 대해 {max(그 위치의 높이값, 이전, 즉 현재 위치까지에서의 최대높이값), 새로운행, 새로운열}을 새로 넣고 방문처리 하는것이다.

 

높이기준 최소힙으로 올라가야 그 컴포넌트의 최소벽높이를 알 수 있다.

 

코드

C++

#define tiii tuple<int, int, int>

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int n = heightMap.size(), m = heightMap[0].size();
        priority_queue<tiii, vector<tiii>, greater<>> pq;
        vector<vector<bool>> visited(n, vector<bool>(m, false));

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                    pq.push({heightMap[i][j], i, j});
                    visited[i][j] = true;
                }
            }
        }

        int ans = 0;
        vector<int> dx = {-1, 1, 0, 0};
        vector<int> dy = {0, 0, -1, 1};

        while (!pq.empty()) {
            auto [height, x, y] = pq.top();
            pq.pop();

            for (int k = 0; k < 4; ++k) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny]) continue;

                trappedWater += max(0, height - heightMap[nx][ny]);

                pq.push({max(height, heightMap[nx][ny]), nx, ny});
                visited[nx][ny] = true;
            }
        }

        return ans;
    }
};