구현 - 14719번: 빗물

맵의 왼쪽 끝과 오른쪽 끝에서 벽이 아닌 곳에서부터 출발해서 벽에 닿을 때까지의 공간에는 빗물이 찰 수 없기 때문에 해당 부분을 bfs로 탐색하여 맵에 표시한 후, 해당 공기 부분과 벽 부분이 제외된 맵에서 0의 갯수(=빗물 총량)만 카운트했다.

from collections import deque

h, w = map(int, input().split())
blocks = list(map(int, input().split()))

# w * h 크기의 맵
maps = [[0] * w for _ in range(h)]

for idx, val in enumerate(blocks):
    for i in range(val):
        maps[i][idx] = 1 # 맵에 벽 설치 (상하 반전 상관없음)


# dir=0: 우측, dir=1: 좌측
dx = [0, 0] 
dy = [1, -1]

def bfs(x, y, maps, visited):
    queue = deque()
    queue.append((x, y))
    visited.add((x, y))
    maps[x][y] = 2
    dir = 0

    if y == 0: # 우측으로 벽을 만날 때까지 탐색
        dir = 0
    else: # 좌측으로 벽 만날 때까지 탐색
        dir = 1

    while queue:
        x, y = queue.popleft()
        nx, ny = x + dx[dir], y + dy[dir]

        # 맵 밖이 아니면서 벽이 아니면서 방문하지 않은 곳이라면
        if 0 <= nx < h and 0 <= ny < w and maps[nx][ny] == 0 and (nx, ny) not in visited:
            maps[nx][ny] = 2
            queue.append((nx, ny))
            visited.add((nx, ny))
    
    return



visited = set()

# 맵 속 벽과 빗물 제외한 공기 제거 (맵에 2로 표기)
for i in range(h):
    # 맵의 가장 좌측 중 0인 좌표
    if maps[i][0] == 0:
        bfs(i, 0, maps, visited)
    # 맵의 가장 우측 중 0인 좌표
    if maps[i][w - 1] == 0:
        bfs(i, w - 1, maps, visited)


#for i in range(h):
#    print(maps[i])

rain_sum = 0
# 빗물 세기 (맵의 0 갯수 세는 것과 동일)
for i in range(h):
    rain_sum += maps[i].count(0)

print(rain_sum)