백준 14719 - 빗물 (파이썬)

https://www.acmicpc.net/problem/14719

풀이

주어진 블록 배치에서 빗물이 고이는 양을 구하는 문제이다.

문제에서는 2차원 격자를 생성해서 풀어야 하기 떄문에 다음과 같이 선언하였다.

B = [[0] * W for _ in range(H)]

블록을 채우기 위해서 다음과 같이 수행한다.

for i in range(H) :
    for j in range(A[i]) :
        B[H - 1 - j][i] = 1

1. 각 열(i)에서 블록의 높이만큼(A[i]) 1을 채운다.
2. (H - 1 - j, i) 위치를 1로 설정해서 바닥부터 쌓이도록 만든다.

빗물을 계산하기 위해서 다음과 같이 수행한다.

count = 0
for i in range(H):
    for j in range(W):
        if B[i][j] == 1:
            continue

즉, 격자를 한 칸씩 탐색하면서 0인칸(빈공간)을 확인한다.

왼쪽 벽 확인을 위해서 다음과 같이 수행한다.

k = j
while k >= 0:
    if B[i][k] == 1:
        break
    k -= 1

if k == -1:
    continue  # 왼쪽에 벽이 없으면 물이 안 고임

1. 현재 위치에서 왼쪽 방향으로 이동하며 1을 찾는다.
2. 왼쪽 끝까지 가도 1이 없다면 이 위치에는 빗물이 안고이므로 건너뜀

오른쪽 벽 확인을 위해서 다음과 같이 수행한다.

k = j
while k < W:
    if B[i][k] == 1:
        break
    k += 1

if k == W:
    continue  # 오른쪽에 벽이 없으면 물이 안 고임

1. 현재 위치에서 오른쪽 방향으로 이동하며 1을 찾는다.
2. 오른쪽 끝까지 가도 1이 없다면 이 위치에는 빗물이 안고이므로 건너뛴다.

오른쪽과 왼쪽 벽이 모두 존재하면 빗물이 고이는 공간이므로 count를 증가한다.

코드

# 백준 14719 - 빗물
# 분류 : 브루트 포스

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

B = [[0] * W for _ in range(H)]

for i in range(H) :
    for j in range(A[i]) :
        B[H - 1 - j][i] = 1

count = 0
for i in range(H) :
    for j in range(W) :
        if B[i][j] == 1 :
            continue
        
        k = j
        while k >= 0 :
            if B[i][k] == 1 :
                break
            k -= 1
        
        if k == - 1 :
            continue

        k = j
        while k < W :
            if B[i][k] == 1 :
                break
            k += 1
        
        if k == W :
            continue

        count += 1

print(count)