백준 14719 - 빗물 (파이썬)

문제

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

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

입력

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

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

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

출력

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

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

 

# 해결법

 

문제에서 바닥은 막혀있다고 가정했고 빗물이 고이기 위해서는 빈 부분의 양 옆으로 막힌 부분이 있어야한다는 점을 주목했다. 

우선 블록의 막힌 부분은 True, 빈 부분은 False로 나타내는 blocked[][] 리스트를 만들었다.

그리고 blocked 리스트를 왼쪽에서 오른쪽으로 진행하며 현재 값이 True라면(막혀있다면) 다음 블록이 비어 있을때 비가 고일 가능성을 + 1 해주고, 가로를 오른쪽으로 한칸씩 이동한다.

비어 있는 블록을 만날때마다 가능성을 +1 해주다가 다시 막혀있는 블록을 만나게 된다면 비의 갯수에 비 가능성을 더해준다.

만약 다시 막혀있는 블록을 만나지 못한다면 비 가능성을 0으로 초기화 시키고 세로 인덱스를 이동한다.

처음 구현한 코드도 이상없이 작동했는데 for 문의 중첩이 많고, 딱히 함수를 쓴 의미가 없는 코드인 것 같아서 재귀함수를 사용한 코드를 두번째로 작성해보았다.

비의 가능성 초기화가 두번 등장하는 이유는 양 옆이 막혀서 가능성을 갯수에 더해줄때와 오른쪽 끝이 막히지 않아서 세로 인덱스가 다음으로 넘어갔을 때, 둘 다 초기화를 시켜줄 필요가 있기 때문이다.

 

 

# 나의 코드

def rain(x, y):
    global rain_cnt
    global rain_possible

    for k in range(x-1,-1,-1): # 세로 길이의 아래서부터 위로 반복
        for l in range(y): # 가로 길이 반복        
        
            if blocked[k][l]: # 막혔다면
                rain_possible = 0 # 비의 가능성 0으로 초기화
                
                for m in range(l+1,y): # 막힌 블록의 오른쪽으로 진행
                
                    if blocked[k][m]: # 블록이 막혔다면
                        rain_cnt += rain_possible # 비 숫자에 비 가능성을 더함
                        rain_possible = 0 # 비 가능성 초기화
                        break # 탈출                        
                    elif not blocked[k][m]: # 블록이 막히지 않았다면
                        rain_possible += 1 # 비 가능성 + 1

a, b = map(int, input().split()) # a가 세로 길이, b가 가로 길이
high_list = list(map(int, input().split())) # 높이 리스트
blocked = [[False for _ in range(b)] for _ in range(a)] # 가로 * 세로 모두 False로 채움

for i in range(b): # 가로 길이만큼 반복
    for j in range(a-1,a-high_list[i]-1,-1): # 세로 길이를 아래서부터 높이 리스트만큼 반복
        blocked[j][i] = True # 막힌 부분은 True로 바꿈
        
rain_cnt = rain_possible = 0
rain(a,b) # 함수 호출
print(rain_cnt)

# 수정 코드

def rain(x, y):
    global rain_possible
    global rain_cnt
    if y == b - 1: # 가로의 끝이라면
        rain_possible = 0 # 비 가능성을 0으로 초기화 
        return # 리턴
    elif not blocked[x][y+1]: # 다음 블록이 막히지 않았다면
        rain_possible += 1 # 비 가능성 + 1
        rain(x, y + 1) # 다음 블록에 대한 함수 호출
        return
    elif blocked[x][y+1]: # 다음 블록이 막혔다면
        rain_cnt += rain_possible # 비 갯수에 비 가능성을 더하고
        rain_possible = 0 # 비 가능성 초기화
        return
    return

a, b = map(int, input().split()) # a가 세로 길이, b가 가로 길이
high_list = list(map(int, input().split())) # 높이 리스트
blocked = [[False for _ in range(b)] for _ in range(a)] # 가로 * 세로 모두 False로 채움
rain_cnt = rain_possible = 0

for i in range(b): # 가로 길이만큼 반복
    for j in range(a - 1, a - high_list[i] - 1, -1): # 세로 길이를 아래서부터 높이 리스트만큼 반복
        blocked[j][i] = True # 막힌 부분은 True로 바꿈

for i in range(a): # 세로 길이만큼 반복
    for j in range(b): # 가로 길이만큼 반복
        if blocked[i][j] == True: # 막혔다면
            rain(i,j) # 함수 호출
print(rain_cnt)