[백준] 14719 - 빗물 (Python)

문제 링크

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

알고리즘

• 구현
• 시뮬레이션

입력

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

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

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

출력

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

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

입력 예

4 8
3 1 2 3 4 1 1 2

출력 예

5

입출력 예에 대한 설명

풀이

1. 주어진 H와 W을 이용해서 2차원 리스트를 생성한다.
2. 생성한 리스트에 블록을 집어넣는다.
3. 모든 좌표를 순회하면서 좌표 좌우에 블록이 존재하는지 확인 후 결과값에 1을 추가한다

코드

import sys

input = sys.stdin.readline

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

# 2차원 세계 생성 (블록은 True, 빈공간은 False)
world = [[False for _ in range(W)] for _ in range(H)]
for w in range(W):
    for h in range(H):
        if h >= H - blocks[w]:
            world[h][w] = True

rain = 0

# 모든 좌표를 순회
# 좌표값이 False 이고 좌우에 True가 하나라도 있으면 1추가
# index(True)가 오류날 것을 대비해 try 구문 사용
for i in range(H):
    for j in range(W):
        try:
            if world[i][j] == False and world[i].index(True) < j < (W - 1) - world[i][::-1].index(True):
                rain += 1
        except:
            continue
print(rain)