📚 빗물

문제

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

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

입력

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

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

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

출력

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

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

예제 입력 1 복사

4 4
3 0 1 4

예제 출력 1 복사

예제 입력 2 복사

4 8
3 1 2 3 4 1 1 2

예제 출력 2 복사

예제 입력 3 복사

3 5
0 0 0 2 0

예제 출력 3 복사

힌트

힌트 1:

힌트 2:

힌트 3:

✍ 접근

처음에는 BFS로 양쪽이 막혀있는 부분을 탐색하려고 했다.
손코딩을 해보면서 더 적절한 방법이 있다는 것을 알아냈다.
H와 W가 최대 500이라는 것에 착안해서 이중 for문을 돌리기로 했다. + 투포인터

정답코드

import sys
input = sys.stdin.readline
H,W = map(int,input().split())
arr = list(map(int,input().split()))

cnt = 0
for h in range(H):
    lt = 0
    rt = W-1
    while lt<=rt:
        if arr[lt]==0:
            lt+=1
        elif arr[rt] ==0:
            rt-=1
        if arr[lt]!=0 and arr[rt]!=0:
            break
        if lt == rt:
            break
    for x in arr[lt:rt]:
        if x == 0:
            cnt+=1
    for w in range(W):
        if arr[w]>0:
            arr[w]-=1

print(cnt)

해설

문제에서 나온 값을 입력받는다
높이를 돌리면서 포인터로 이용할 lt와 rt를 0와 W-1로 잡는다
- lt <= rt일때 while문을 돌리면서
  만약 lt가 0이면 lt+=1
  rt가 0이면 rt-=1로
  범위를 좁혀준다
  - 만약 lt와 rt가 둘 다 0이 아니라면 이 사이에 있는 0은 다 물이 고일 수 있는 곳이기 때문에 break로 while문을 빠져나가준다
  - 만약 lt와 rt가 같아도 break로 빠져나간다. lt와 rt가 만날때까지 0이라는 사실은 더이상 빗물이 고일 수 없는 상황이기 때문이다
- 그 후 lt부터 rt까지
  ((lt,rt-1) 혹은 (lt+1, rt-1)도 상관없다. 이유 = 어차피 lt와 rt는 0이 아니기 때문에)
  돌려주면서 0을 발견하면 cnt+=1을 해준다
- 마지막으로 다음 라인 검사를 위해 가로를 돌리면서 0보다 큰 값이 있을 때 1씩 빼준다

⭐ 배움

for문을 잘 활용하기 + 투포인터 쓰기

저작자표시