[백준 14719] - 빗물(C++)[골드5]

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

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

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

---

🔎문제 해석

빗물이 고이는 조건, 상황을 잘 생각해보면 쉽게 풀 수 있는 문제다.
특정 칸을 기준으로 왼쪽방향에서 가장 높은 기둥과, 오른쪽 방향에 가장 높은기둥의 높이를 구해준다.
빗물은 왼쪽,오른쪽 방향의 가장 높은기둥 중 더 작은 방향의 기둥 높이만큼 빗물이 고인다.

 

예시를 들어서 설명해보겠습니다.

빗물이 고이기 전 사진입니다.

과정은 아래와 같습니다.

1. 각 지점에서 왼쪽방향, 오른쪽 방향으로 가장 높은기둥의 높이를 찾습니다.
2. 첫 번째 화살표 지점에서는 왼쪽방향은 3 / 오른쪽방향은 4가 될 것입니다.
3. 그렇다면 빗물은 왼쪽과 오른쪽 중 더 작은 높이인 왼쪽방향의 기둥 높이만큼 고이게 될 것입니다.
   1. 고이는 빗물의 양은 3번에서 구한 높이에서 본인의 기둥높이를 뺀 만큼 빗물이 고이게 됩니다.
   2. 만약 3번 과정에서 구한 높이에서 본인의 기둥높이를 뺏는데, 음수가 나온다면 그 위치는 빗물이 고이지 못합니다.
      1. 예를 들어서 기둥의 높이가 4인 것을 기준으로 탐색을 시작합니다.
         1. 왼쪽 기둥 : 3 / 오른쪽 기둥: 3이 될 것입니다.
         2. 둘 다 높이가 같기 때문에 3-4 = -1만큼 고이게 될 것입니다.
         3. 하지만 여기서 -1만큼 고인다는 말은 없기에, 해당 기둥에서는 빗물이 고이지 못하는 것입니다.
4. 이렇게 각 지점마다 왼쪽, 오른쪽으로 탐색을 해서 본인의 기둥에서 작은 높이의 기둥높이만큼 뺀 값을 계속 더해주면 됩니다.

모든 과정을 끝낸 후 아래와 같은 모양이 될 것입니다.

 

💻코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int h, w; // h세로, w 가로
vector<int> rain;
int main()
{
    cin >> h >> w;
    rain.resize(w, 0);
    for (int i = 0; i < w; i++)
    {
        cin >> rain[i];
    }
    int total =0;
    for(int i=0;i<w; i++){ 
        int left = 0,right = 0;
        for(int j=0; j<i; j++){ //기준점의 왼쪽방햐엥서 가장 높은 기둥의 높이 구하기
            left =max(left,rain[j]);
        }
        for(int j=w-1; j>i; j--){ //기준점의 오른쪽방향에서 가장 높은 기둥의 높이 구하기
            right = max(right,rain[j]);
        }
        //다 돌면 기준점마다 왼쪽방향에서 가장 큰값, 오른쪽 방향에서 가장 큰 값을 뽑아냄.
        if(min(left,right)-rain[i]>=0){ //값이 0보다 크다면 담을수 있다는 뜻임..
            total+=min(left,right)-rain[i]; //왼쪽,오른쪽중 더 낮은 높이의 기둥만큼 물이 고임.
        }
    }
    cout<<total<<endl;
}

 

😀느낀 점

• 빗물이 고인다는 그 상황 자체를 이해하면 쉽게 풀 수 있는 문제다.