백준 문제 풀이 - 빗물 14719번

📜 문제 이해하기

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

💡 문제 재정의

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.
빗물이 전혀 고이지 않을 경우 0을 출력하여라.

✏️ 계획 수립

아래서부터 만약 빈공간이 있다면 왼쪽과 오른쪽을 탐색해본다. 만약 왼쪽 오른쪽이 둘다 벽으로 막혀있다면 그 부분을 빗물로 채워준다. 만약 범위를 벗어날때까지 벽을 탐지못하면 빗물이 있을 수 없으므로 빗물을 채우지 않는다. 위 과정을 모든 원소에서 반복한다.

💻 계획 수행

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int width, height, block;
    cin >> height >> width;
    vector<vector<int>> grid(height, vector<int>(width, 0));
    
    // i가 width j가 height
    for (int i=0; i<width; i++){
        cin >> block;
        for (int j=0; j<block; j++)
            grid[j][i] = 1;
    }

    for (int h=0; h<height; h++) {
        for (int w=0; w<width; w++) {
            if (grid[h][w] == 0){
                // 빗물이 흘러 가는 걸 구현
                int right_w = w + 1;
                int left_w = w - 1;
                bool go_right = true;
                bool go_left = true;
                bool right_wall = false;
                bool left_wall = false;
                while (go_right || go_left){
                    if (right_w < width) {
                        if (grid[h][right_w] == 1){
                            go_right = false;
                            right_wall = true;
                        }
                        else{
                            right_w += 1;
                        }
                    }
                    else {
                        go_right = false;
                    }
                    if (left_w >= 0) {
                        if (grid[h][left_w] == 1) {
                            go_left = false;
                            left_wall = true;
                        } else {
                            left_w -= 1;
                        }
                    }
                    else {
                        go_left = false;
                    }
                }
                if (right_wall && left_wall)
                    grid[h][w] = 2;
            }
        }
    }
    int rain_sum = 0;

    for (int h = 0; h < height; h++) {
        for (int w = 0; w < width; w++) {
            if (grid[h][w] == 2)
                rain_sum += 1;
        }
    }

    cout << rain_sum << endl;
}

🤔 회고

특정한 자료 구조를 사용하는것이 아니라 구현에 관련된 문제였다. 문제 해결 방법만 세우고 그걸 코드로 옮기는게 중요한 것 같다.