← All Articles

[BAEKJOON] 14719. 빗물

Posted on

문제 :

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

image

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


입력 :

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

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

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


출력 :

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

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



풀이 :

예전에 풀다가 마땅한 로직이 떠오르지 않아 남겨두고 있던 문제였다.

실력 점검차 못풀었던 문제들을 살펴보다 이 문제를 발견하고 풀어보았고, 생각보다 빠르게 로직을 생각해낸 것 같다.

그리 어려운 문제는 아니였으나, 그 때 당시에는 잘 접근하지 못한 기억에 남는 문제이다.


[ 세부 구현사항 ]

  1. 가로축을 중심으로 한 지점을 가정해보면 왼쪽과 오른쪽 각각에 자신보다 더 높은 벽이 있어야 물이 고일 수 있다. 이 점을 캐치해내면 사실 문제는 쉽게 해결할 수 있다.
  2. 양쪽에 자신보다 높은 벽이 위치해 있는지 확인하기 위해서 왼쪽 편의 가장 높은 벽을 저장하는 lefthighest[] 배열과 오른쪽 편의 가장 높은 벽 높이를 저장하는 righthighest[] 배열을 만든다.

  3. 양쪽 최대 높이 벽을 모두 구하게 되면 해당 가로 인덱스의 고이는 빗물의 양은 min(lefthighest[i], righthighest[i]) - blocks[i] 가 된다.


예전에 풀지 못했던 문제, 혹은 풀었던 문제를 다시 풀어보면서 공부를 정리해봐도 좋을 듯 하다!



코드 :

코드 보기/접기 
#include <iostream>
#include <algorithm>

using namespace std;
int height, width, blocks[500], lefthighest[500], righthighest[500];

int main() {
    int watersum = 0;
    cin >> height >> width;

    for (int i = 0; i < width; i++)
        cin >> blocks[i];

    int curhigh = blocks[0];
    lefthighest[0] = blocks[0];
    for (int i = 1; i < width; i++) {
        curhigh = max(curhigh, blocks[i]);
        lefthighest[i] = curhigh;
    }

    curhigh = blocks[width - 1];
    righthighest[width - 1] = blocks[width - 1];
    for (int i = width - 2; i >= 0; i--) {
        curhigh = max(curhigh, blocks[i]);
        righthighest[i] = curhigh;
    }

    for (int i = 0; i < width; i++)
        watersum += min(lefthighest[i], righthighest[i]) - blocks[i];

    cout << watersum << '\n';
    return 0;
}


AlgorithmalgorithmbaekjoonC++