[백준 14719] 빗물

문제

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

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

 

입력

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

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

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

 

출력

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

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

---

접근

기본적인 틀은 다음과 같다.

물이 고이는 부분은 특정 위치에서 양쪽에 더 높은 블록이 있는 부분이다. 그렇다면 이 부분을 어떻게 찾을까?

높이가 증가하는 부분을 찾고 그 부분부터 이전 블록까지의 거리를 구하고 => 이전 블록을 기준으로 양측에서 작은 높이를 찾는다. => 이를 통해 물의 총량을 구한다.

 

높이가 증가하는 부분을 찾고 이전 블록들을 검사를 편하게 하기위해 스택을 활용한다.

 

구현

높이와 너비를 입력받고 블록들의 높이를 block이라는 리스트에 저장한다.

그리고 block을 탐색하면서 스택에 인덱스를 넣어서 이전 높이들을 꺼내오도록 한다.

H, W = map(int, input().split())
block = list(map(int, input().split()))

stack = []
answer = 0

 

아래의 코드는 높이를 탐색하면서 물의 총량을 구하는 것이다.

- 기본적으로 스택에 현재 인덱스를 push한다.

- while문을 통해 현재 높이보다 더 높은 블록이 나오거나 블록이 없을 때까지 물의 총량을 구한다.

- 이전 높이에 대한 위치를 가져오고 이를 거리를 구하는데 활용한다.

- 이후 양측의 높이 중 작은 높이만큼 물이 차기 때문에 작은 높이를 가져오고 이를 현재 높이만큼 빼준다.

- 위에서 구한 거리와 높이를 토대로 양을 구하고 최종해에 더한다.

for i in range(W):
    # 스택이 비어있지 않고 (이전 높이들이 존재함)
    # 현재 높이가 이전 높이보다 크다면 (변곡점, 기준이 됨)
    while stack and block[i] > block[stack[-1]]:
        # 이전 블록의 인덱스를 top에 저장
        top = stack.pop() 
        
        # 꺼냈을 때 스택이 빈다면 물이 찰 수가 없음
        if not stack:
            break
        
        # 거리구하기
        distance = (i - stack[-1]) - 1
        # 높이구하기
        height = min(block[i], block[stack[-1]]) - block[top]

        answer += (distance * height)
    stack.append(i)

---

전체 코드

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
block = list(map(int, input().split()))

stack = []
answer = 0
for i in range(W):
    # 스택이 비어있지 않고 (이전 높이들이 존재함)
    # 현재 높이가 이전 높이보다 크다면 (변곡점, 기준이 됨)
    while stack and block[i] > block[stack[-1]]:
        # 이전 블록의 인덱스를 top에 저장
        top = stack.pop()

        # 꺼냈을 때 스택이 빈다면 물이 찰 수가 없음
        if not stack:
            break

        # 거리구하기
        distance = (i - stack[-1]) - 1
        # 높이구하기
        height = min(block[i], block[stack[-1]]) - block[top]

        answer += (distance * height)
    stack.append(i)

print(answer)