백준 빗물 14719번 파이썬 풀이

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

14719번: 빗물

 

 

코드

# 빗물
import sys
si = sys.stdin.readline

answer = 0
N, M = map(int, si().split())
height_list = list(map(int, si().split())) # 3 1 2 3 4 1 1 2
graph = [[0 for _ in range(M)] for __ in range(N)]

# 벽 초기화
for i in range(len(height_list)):
    for j in range(N-1, (N-1) - height_list[i], -1):
        graph[j][i] = 1 # 벽은 1으로 한다.

# 탐색 시작
for i in range(N-1, -1, -1): # 1층부터 탐색 3 -> 2 -> 1 -> 0
    # 첫번째가 기둥인지 아닌지
    if graph[i][0] == 1: 
        isFirstWall = True
    else: 
        isFirstWall = False
    
    tmp = 0
    for j in range(1, M): # 우측으로 가면서 체크 0 -> 1 -> 2 -> 3 -> 4 ...
        if isFirstWall: # 첫번째가 기둥이면 count가 가능하다.
            if graph[i][j] == 0: # 물을 담을 수 있다면
                tmp += 1
            else: # 벽이라면
                answer += tmp
                tmp = 0
        else: # 첫번째가 기둥이 아니라면 다음 기둥을 찾아야 한다.
            if graph[i][j] == 1:
                isFirstWall = True

print(answer)

 

풀이

벽인 것은 1로 초기화해 graph를 구성하였다.

벽 초기화

 

 

만약 현재 벽이고 그 다음이 비어있다면, 물이 담길 수 있다. 예를 들어, 2층의 1 2 3열에서 벽-공간-벽으로 구성되어있으므로 물이 담길 수 있다. 여기서 착안해 아이디어를 떠올릴 수 있다. 만약 우측으로 이동하면서 빗물이 담길 수 있는 빈 공간의 경우를  임시로 count하고, 벽인 경우 값을 answer에 담고 임시 값 tmp를 초기화하는 것이다. 하지만 이 로직에 예외사항이 있는데, 이는 첫번째 열이다. 각 층의 첫번째 열은 특별하다. 왜냐하면 첫번 째 열이 벽이 아닌 경우엔 우측으로 탐색하면서 빈공간이 있다고 해도, 물이 담길 수 없기 때문이다. 따라서 isFirstWall로 따로 값을 체크했다.

 

첫번째가 벽이 아니다가도, 탐색을 하다 벽을 만나면 이제 첫번째 열에 벽이 있었던것과 논리적으로 동일해진다. 우측으로 이동하면서 빗물이 담길 수 있는 빈공간이 생기기 때문이다. 

 

공통된 논리인 우측으로 가면서 벽인지 아닌지를 체크해 값을 추가하는 로직에, 첫번째 열만 벽인지 아닌지를 체크하는 예외사항 두어 문제를 해결하였다.