[백준] 14719번: 빗물 (Python)

문제 링크

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

14719번: 빗물

 

풀이

풀이 설명

• 이중 배열을 만들어 벽은 1, 빈곳은 0 설정
• 양쪽이 벽으로 둘러싸여야 빗물이 고이므로, 현재 좌표 기준 왼쪽이 벽이고 현재가 비어있으면 현재 좌표를 리스트(starts)에 넣는다.
• 오른쪽으로만 탐색(bfs)하여 벽과 부딪힌 경우만 result에 빈 칸의 수를 넣는다. 

풀이 코드

n, m = map(int, input().split())
walls = list(map(int, input().split()))

# input 값 정리
# h, w 만큼 2차원 배열 만들기
graph = [[0] * m for _ in range(n)]

for j in range(len(walls)):
    for i in range(n-1, n-1-walls[j], -1):
        graph[i][j] = 1

starts = []
for i in range(n):
    for j in range(1, m):
        if graph[i][j] == 0 and graph[i][j-1] == 1:
            starts.append((i, j))

result = 0
for x, y in starts:
    cnt = 1

    while y + 1 < m:
        y += 1
        if graph[x][y] == 0:
            cnt += 1
        if graph[x][y] == 1:
            result += cnt
            break

print(result)