[Gold V] 빗물 - 14719

[Gold V] 빗물 - 14719

문제 링크

성능 요약

메모리: 34052 KB, 시간: 116 ms

분류

구현, 시뮬레이션

제출 일자

2024년 11월 12일 22:28:08

문제 설명

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

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

입력

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

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

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

출력

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

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

 

 

풀이

무엇이 문제인가

빗물이 고이는 양을 구해야한다.

• 첫번째 줄 : 세로길이 H 가로길이 W

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

• 두번째 줄 : 블록이 쌓인 높이를 의미

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

 

스택을 이용하면 벽 사이의 빗물을 구할 수 있다. 

import sys
from collections import deque
sys.stdin = open("input.txt","r")


H , W = map(int, sys.stdin.readline().split())

mat = [[0] * W for _ in range(H)]
visited = [[False] * W for _ in range(H)]

lst = list(map(int, sys.stdin.readline().split()))

for i in range(len(lst)):
    h = lst[i]
    for idx in range(h):
        mat[idx][i] = 1

for _ in mat:
    print(_)

result_lst = []
for i in mat:
    z_s = deque()
    o_s = deque()
    count = 0
    for _ in range(W):
        element = i.pop()
        # 이미 벽(1)이 있을 경우에만 z_s(제로 스택)에 append()
        if(element == 0 and len(o_s)%2==1):
            z_s.append(1)
        elif(element == 1):
            o_s.append(1)
        
        # 벽(1)이 짝이 지어지면, 나머지 하나의 벽(최근 벽)은 사라지고 z_s에 있는 모든 값들을 pop 
        if(len(o_s) != 0 and len(o_s)%2==0):
            o_s.pop()
            while(z_s):
                count += z_s.pop()
                
                
    result_lst.append(count)


print(sum(result_lst))