[알고리즘] BOJ 14719 빗물

[BOJ] 14719 빗물 바로가기

📍 문제

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

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

---

📍 입력

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

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

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

---

📍 출력

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

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

---

📍 풀이

✍ 문제 풀이

• 각 위치의 블록들에 고이는 빗물의 경우를 모두 구하여 값을 더하는 방식을 이용하였다.
• 현재 위치의 블록를 기준으로 왼쪽에 존재하는 블록 중 가장 큰 블록의 값(leftWall)과 오른쪽에 존재하는 블록 중 가장 큰 블록의 값(rightWall)을 구한다.
• leftWall 과 rightWall 은 현재 위치의 블록에 빗물이 고일 수 있도록 만드는 벽과 같다고 볼 수 있다.
• 만약 leftWall 과 rightWall 의 값이 현재 블록의 높이보다 작거나 같다면 현재 블록에는 빗물이 고일 수 없다.
• 반대로 leftWall 과 rightWall 의 값이 현재 블록의 높이보다 높다면 현재 블록에는 빗물이 고일 수 있다.
• 빗물이 고이는 양은 leftWall 과 rightWall 중 더 작은 블록의 높이 값에서 현재 블록의 높이 값만큼을 뺀 값이다.
• 이렇게 구해진 빗물의 양을 result 에 순차적으로 합하여 결과를 출력한다.

✍ 코드

from sys import stdin

def SumOfRainWater(W,blocks):
    result = 0
    for i in range(1,W-1):
        # leftWall : 현재 위치 기준 왼쪽에 존재하는 블록 중 가장 큰 블록
        # rightWall : 현재 위치 기준 오른쪽에 존재하는 블록 중 가장 큰 블록
        # std : 현재 위치에 쌓일 빗물의 양의 계산을 위한 기준
        leftWall, rightWall = max(blocks[:i]), max(blocks[i+1:]) 
        std = min(leftWall,rightWall)
        # std가 현재 위치의 블럭보다 높다면,
        if std > blocks[i]: result += std - blocks[i]
    return result

H, W = map(int,stdin.readline().split())
blocks = tuple(map(int,stdin.readline().split()))
print(SumOfRainWater(W,blocks))