문제 링크

내 코드

Solution 참고

Solution

Approach: BFS + Priority Queue

• 43ms, 18.59MB
• Complexity
  • Let $m$ be the number of rows and $n$ the number of columns of the input grid.
  • Time Complexity: $O(m \cdot n \times \log m \cdot n)$
  • Space Complexity: $O(m \times n)$

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        // Direction arrays
        int dRow[4] = {0, 0, -1, 1};
        int dCol[4] = {-1, 1, 0, 0};

        int numOfRows = heightMap.size();
        int numOfCols = heightMap[0].size();

        vector<vector<bool>> visited(numOfRows, vector<bool>(numOfCols, false));

        // Priority queue (min-heap) to process boundary cells in increasing
        // height order
        priority_queue<Cell> boundary;

        // Add the first and last column cells to the boundary and mark them as
        // visited
        for (int i = 0; i < numOfRows; i++) {
            boundary.push(Cell(heightMap[i][0], i, 0));
            boundary.push(Cell(heightMap[i][numOfCols - 1], i, numOfCols - 1));
            // Mark left and right boundary cells as visited
            visited[i][0] = visited[i][numOfCols - 1] = true;
        }

        // Add the first and last row cells to the boundary and mark them as
        // visited
        for (int i = 0; i < numOfCols; i++) {
            boundary.push(Cell(heightMap[0][i], 0, i));
            boundary.push(Cell(heightMap[numOfRows - 1][i], numOfRows - 1, i));
            // Mark top and bottom boundary cells as visited
            visited[0][i] = visited[numOfRows - 1][i] = true;
        }

        int totalWaterVolume = 0;

        while (!boundary.empty()) {
            // Pop the cell with the smallest height from the boundary
            Cell currentCell = boundary.top();
            boundary.pop();

            int currentRow = currentCell.row;
            int currentCol = currentCell.col;
            int minBoundaryHeight = currentCell.height;

            // Explore all 4 neighboring cells
            for (int direction = 0; direction < 4; direction++) {
                int neighborRow = currentRow + dRow[direction];
                int neighborCol = currentCol + dCol[direction];

                // Check if the neighbor is within the grid bounds and not yet
                // visited
                if (isValidCell(neighborRow, neighborCol, numOfRows,
                                numOfCols) &&
                    !visited[neighborRow][neighborCol]) {
                    int neighborHeight = heightMap[neighborRow][neighborCol];

                    // If the neighbor's height is less than the current
                    // boundary height, water can be trapped
                    if (neighborHeight < minBoundaryHeight) {
                        totalWaterVolume += minBoundaryHeight - neighborHeight;
                    }

                    // Push the neighbor into the boundary with updated height
                    // (to prevent water leakage)
                    boundary.push(Cell(max(neighborHeight, minBoundaryHeight),
                                       neighborRow, neighborCol));
                    visited[neighborRow][neighborCol] = true;
                }
            }
        }

        return totalWaterVolume;
    }

private:
    // Struct to store the height and coordinates of a cell in the grid
    class Cell {
    public:
        int height;
        int row;
        int col;

        // Constructor to initialize a cell
        Cell(int height, int row, int col)
            : height(height), row(row), col(col) {}

        // Overload the comparison operator to make the priority queue a
        // min-heap based on height
        bool operator<(const Cell& other) const {
            // Reverse comparison to simulate a min-heap
            return height >= other.height;
        }
    };

    // Helper function to check if a cell is valid (within grid bounds)
    bool isValidCell(int row, int col, int numOfRows, int numOfCols) {
        return row >= 0 && col >= 0 && row < numOfRows && col < numOfCols;
    }
};

GPT (o3-mini-high)

이 코드는 “Trapping Rain Water II” 문제를 해결하는 전형적인 알고리즘을 구현한 것입니다.
문제의 목표는 2차원 그리드에서, 각 셀의 높이가 주어졌을 때 비가 고일 수 있는 총 물의 양을 구하는 것입니다.
이 솔루션은 우선순위 큐(최소 힙) 를 사용하여 경계(boundary) 셀부터 내부로 확장하면서,
높이의 최소값을 기준으로 물이 채워질 수 있는 양을 계산합니다.

다음은 코드의 주요 구성 요소와 동작 방식에 대한 자세한 설명입니다.

---

1. 방향 벡터 및 그리드 정보

// 방향 배열: 왼쪽, 오른쪽, 위, 아래 (grid 값 1,2,3,4와는 별개로, 이 코드는
// 인접 셀 탐색을 위해 dRow, dCol 사용)
int dRow[4] = {0, 0, -1, 1};
int dCol[4] = {-1, 1, 0, 0};

int numOfRows = heightMap.size();
int numOfCols = heightMap[0].size();

• dRow와 dCol 배열은 현재 셀에서 상하좌우 네 방향의 이웃 셀 좌표를 계산하기 위해 사용합니다.
• numOfRows와 numOfCols는 그리드의 행과 열의 개수를 저장합니다.

---

2. 방문 여부 배열 및 우선순위 큐 초기화

vector<vector<bool>> visited(numOfRows, vector<bool>(numOfCols, false));
priority_queue<Cell> boundary;

• visited: 각 셀을 한 번만 처리하기 위해 방문 여부를 기록합니다.
• boundary:
  • Cell 구조체를 저장하는 우선순위 큐로, 셀의 높이에 따라 오름차순(최소 힙)으로 정렬됩니다.
  • 여기서 Cell은 (높이, 행, 열)을 저장하며, 비교 연산자 <를 오버로딩하여 낮은 높이일수록 우선순위가 높도록 구현되어 있습니다.

---

3. 경계 셀 초기화

// 좌우 경계 셀 추가 및 방문 처리
for (int i = 0; i < numOfRows; i++) {
    boundary.push(Cell(heightMap[i][0], i, 0));
    boundary.push(Cell(heightMap[i][numOfCols - 1], i, numOfCols - 1));
    visited[i][0] = visited[i][numOfCols - 1] = true;
}

// 상하 경계 셀 추가 및 방문 처리
for (int i = 0; i < numOfCols; i++) {
    boundary.push(Cell(heightMap[0][i], 0, i));
    boundary.push(Cell(heightMap[numOfRows - 1][i], numOfRows - 1, i));
    visited[0][i] = visited[numOfRows - 1][i] = true;
}

• 경계 셀 초기화:
  • 그리드의 가장자리(좌측, 우측, 상단, 하단)의 셀들은 외부와 직접 연결되어 있으므로,
    이들은 비가 고일 수 없는 “경계”로 간주됩니다.
  • 이 경계 셀들을 우선순위 큐에 삽입하고, visited 배열에 방문 처리합니다.

---

4. 우선순위 큐(최소 힙)를 이용한 탐색 및 물 채우기

int totalWaterVolume = 0;

while (!boundary.empty()) {
    Cell currentCell = boundary.top();
    boundary.pop();

    int currentRow = currentCell.row;
    int currentCol = currentCell.col;
    int minBoundaryHeight = currentCell.height;

    // 현재 셀의 4방향 이웃 셀 탐색
    for (int direction = 0; direction < 4; direction++) {
        int neighborRow = currentRow + dRow[direction];
        int neighborCol = currentCol + dCol[direction];

        if (isValidCell(neighborRow, neighborCol, numOfRows, numOfCols) &&
            !visited[neighborRow][neighborCol]) {

            int neighborHeight = heightMap[neighborRow][neighborCol];

            // 현재 경계의 높이보다 이웃 셀의 높이가 낮다면, 해당 높이 차이만큼 물이 고일 수 있음
            if (neighborHeight < minBoundaryHeight) {
                totalWaterVolume += minBoundaryHeight - neighborHeight;
            }

            // 물이 채워진 후의 유효 높이는, 이웃 셀의 원래 높이와 현재 경계 높이 중 더 큰 값
            boundary.push(Cell(max(neighborHeight, minBoundaryHeight),
                               neighborRow, neighborCol));
            visited[neighborRow][neighborCol] = true;
        }
    }
}

• 우선순위 큐 처리:

  • 큐에서 높이가 가장 낮은 셀을 꺼내어, 해당 셀을 기준으로 인접한 이웃 셀을 검사합니다.
  • minBoundaryHeight는 현재 경계의 최소 높이로, 이 값보다 낮은 이웃 셀에는 물이 고이게 됩니다.

• 물의 채움 계산:

  • 만약 이웃 셀의 높이가 현재 경계보다 낮으면,
    $\text{minBoundaryHeight} - \text{neighborHeight}$만큼 물이 채워질 수 있습니다.
  • 그 후, 이웃 셀을 경계에 넣을 때는 물이 채워진 후의 높이(즉, $\max(\text{neighborHeight}, \text{minBoundaryHeight})$)로 처리하여
    물이 더 넘치지 않도록 합니다.

• 방문 처리:

  • 이웃 셀을 처리한 후에는 visited 배열에 표시하여 중복 방문을 막습니다.

---

5. 최종 결과 반환

return totalWaterVolume;

• 탐색이 종료되면, 우측 하단까지 도달하는 동안 채워진 총 물의 양이 totalWaterVolume에 누적되어 있습니다.
• 이 값이 최종적으로 반환됩니다.

---

결론

• 핵심 아이디어:

  • 경계 셀부터 시작하여 내부로 확장하면서,
    현재 경계의 최소 높이를 기준으로 인접 셀에 얼마만큼의 물이 채워질 수 있는지를 계산합니다.
  • 우선순위 큐를 사용하여 항상 현재 가장 낮은 경계 셀을 기준으로 처리함으로써,
    물이 고일 수 있는 모든 셀에 대해 올바른 물 높이(물의 누적량)를 계산할 수 있습니다.

• 알고리즘 요약:

  1. 그리드의 경계 셀들을 초기 경계로 설정하고 방문 처리한다.
  2. 우선순위 큐(최소 힙)를 사용해 경계 셀을 하나씩 처리하며,
     인접한 셀에 대해 물이 채워질 수 있는 양을 계산하고,
     해당 셀을 새로운 경계로 삽입한다.
  3. 모든 셀이 처리되면, 총 물의 양을 반환한다.

이 솔루션은 표준적인 우선순위 큐 기반의 “Trapping Rain Water II” 알고리즘을 구현한 것으로,
효율적으로 전체 그리드에서 고일 수 있는 물의 총량을 구합니다.