[백준] 14718번 : 빗물

14719번: 빗물

해당 문제는 stack 자료구조를 활용하여 문제를 해결하였습니다.

1. 각각의 열을 순회합니다.
2. 각각의 열의 순회에 대하여 스택에 빗물, 블록을 구분하여 추가합니다.
3. 현재 블록을 만났고, 바로 직전에 빗물이 나왔다면 모든 스택을 꺼냅니다.
4. 모든 스택을 꺼냇음에도 블록이 나오지않았다면 빗물은 가둬질 수 없으므로 무시합니다.
5. 모든 스택을 꺼냇을때 블록이 하나이상 나왔다면 빗물은 가둬질 수 있으므로 가중치에 결과를 누적합니다.

H, W = map(int, input().split())
table = [[0 for _ in range(W)] for _ in range(H)]
temp = list(map(int, input().split()))

for i in range(len(temp)):
    h = temp[i]
    for j in range(h):
        table[j][i] = 1
total = 0
for i in range(H):
    stack = []
    for j in range(W):
        cur = table[i][j] # 현재
        if stack: # 스택에 값이 있는경우
            if stack[-1] == 0 and cur == 1: # 바로이전이 빗물이고, 현재 벽을 만난경우
                cnt = 0
                while stack: # 스택을 모두 꺼냅니다.
                    t = stack.pop()
                    if t == 1: # 벽이 나온경우 종료하고 cnt를 반영한다.
                        total += cnt
                        stack = [] # 스텍을 초기화
                    if t == 0: # 빗물인경우 빗물의 개수를샌다
                        cnt += 1

        stack.append(cur)

print(total)