Leetcode 407. Trapping Rain Water II

문제

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.

• 3D 공간에 도형이 주어질때, 여기에 담을수 있는 물의 최대치를 구하시오
• 주어진 배열은 각 사각형의 높이

예시

[[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]] # 위 사진과 동일

• 사진을 보면 알수 있듯, 총 4칸 ( 1 + 2 + 1 ) 의 물을 넣을수 있다.

제한

• $m == heightMap.length$
• $n == heightMap[i].length$
• $1 <= m, n <= 200$
• $0 <= heightMap[i][j] <= 2 * 10^4$

풀이

• 준비
  • 먼저 높이와 행, 열 값을 저장할수 있는 Min heap을 하나 만든다.
    • 다만 Heap을 꺼내는 기준은 높이가 된다.
  • 또한 순회를 할 예정이기 때문에 순회가 이미 된 블럭들을 저장할 set도 하나 필요하다.
    • visited정도로 이름 붙히면 될 것 같다.

1. 가장자리 블럭들을 Heap에 먼저 다 집어넣기
   • 이 블럭들이 우리가 빗물을 가둬놓을수 있는 칸을 구할수 있는 힌트가 된다.
2. 가장자리 블럭중에서 가장 낮은 높이를 가진 블럭을 Heap에서 꺼낸다.
3. 그 블럭에서 상하좌우로 탐색한다.
   a. 만약 탐색한 블럭이 자신보다 크다면? -> 그 블럭은 새로운 가장자리가 되어 바로 heap에 넣는다.
   b. 만약 탐색한 블럭이 자신보다 작다면 -> 나머지 가장자리도 자신보다 크거나 같기 때문에 그곳에는 반드시 빗물이 들어간다. -> 들어가는 양은 자신의 높이 - 해당하는 블럭의 높이
   - 다만 해당하는 블럭(빗물이 차는 블럭) 을 Heap에 넣을땐 자신을 탐색했던 블럭의 높이를 사용한다. 그렇지 않으면 이 옆에 빗물이 차는 블럭을 볼때 빗물이 차는 양을 실제보다 낮게 보게 된다.
   

예시

[12, 12, 12, 12]   
[12, 4, 8, 12]   
[12, 12, 12, 12]    

가 있을때
2행 4열의 12를 탐색해서 8을 찾아 4칸만큼 물을 채웠다고 했을때
힙에 8을 넣으면 4 부분에선 8칸의 빗물이 들어갈수 있으나 ( 실제로는 )
계산상 4가 될수 있다.
그렇기에 8을 탐색할때 힙에는 그것을 탐색한 최소 높이인 12를 넣어야 한다.

• 이렇게 모든 블럭을 탐사하면서 값을 추가하면 된다.

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        h = []
        visited = set()

        grid = heightMap

        R = len(grid)
        C = len(grid[0])

        # 가장자리 부분 Heap에 넣기
        for r in range(R):
            for c in range(C):
                if r == 0 or c == 0 or r == R - 1 or c == C - 1:
                    heappush(h, (grid[r][c], r, c))
                    visited.add((r, c))

        directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]

        ans = 0

        while h:
            height, row, col = heappop(h)

            # 상하좌우 탐색
            for i in range(4):
                row_dir, col_dir = directions[i]
                to_row = row + row_dir
                to_col = col + col_dir

                if min(to_row, to_col) < 0 or to_row >= R or to_col >= C:
                    continue

                # 이전에 방문하지 않은 경우에만
                if (to_row, to_col) not in visited:
                    # 여기 방문함!
                    visited.add((to_row, to_col))

                    # 만약 높이가 낮다면
                    if grid[to_row][to_col] < height:
                        # 그만큼 정답에 더하고 ( 빗물이 찬 양이니까 )
                        ans += height - grid[to_row][to_col]
                        # 힙에는 탐색에 사용된 높이를 넣는다.
                        heappush(h, (height, to_row, to_col))
                    else:
                        # 더 크다면 그냥 새로운 가장자리가 될수 있도록 해준다.
                        # 그냥 힙에 다시 넣는다는 뜻
                        heappush(h, (grid[to_row][to_col], to_row, to_col))

        return ans