[BOJ] 14719 빗물 Python

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

14719번: 빗물

 

문제

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

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

입력

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

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

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

출력

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

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

 

내 풀이

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
bricks = list(map(int, input().split()))
graph = [[0]*w for _ in range(h)]

for idx, height in enumerate(bricks):
    for i in range(h-1, h-height-1, -1):
        graph[i][idx] = -1 #벽돌 -1로 표기

# 왼쪽부터
for i in range(h):
    if graph[i][0] != 0:
        continue
    for j in range(w):
        if graph[i][j] == 0:
            graph[i][j] = 1
        if graph[i][j] == -1:
            break
# 오른쪽부터
for i in range(h):
    if graph[i][w - 1] != 0:
        continue
    for j in range(w-1, -1, -1):
        if graph[i][j] == 0:
            graph[i][j]= 1
        if graph[i][j] == -1:
            break

ans = 0
for i in range(h):
    ans += graph[i].count(0)

print(ans)

아이디어

그래프 이용, 벽돌이 있는 위치는 -1로 표기, 다른 칸은 모두 0으로 초기화

그림상의 흰 블럭 (물이 채워지지 않는 부분)을 1로 변환한다.

이걸 두 번으로 나눠서 처리했다.

그래프 탐색시 첫 번째 열이 0으로 시작하면 1로 바꾸다가 -1을 만나면 다음 행으로 넘어감

-> 마지막 열에 도달하기 전 벽돌이 있는 경우 한 행을 전부 탐색하지 않음

따라서 행을 왼쪽부터 탐색 / 오른쪽부터 탐색 이렇게 나눠 처리해줬다.

 

풀긴 풀었지만, 더 좋은 풀이가 있을 것 같아 다른 풀이 코드를 찾아보았다.

 

다른 풀이

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

ans = 0
for i in range(1, w - 1):
    left_max = max(world[:i])
    right_max = max(world[i+1:])

    compare = min(left_max, right_max)

    if world[i] < compare:
        ans += compare - world[i]

print(ans)

출처 : https://seongonion.tistory.com/115

[백준] 14719번 빗물 - 파이썬(Python)