백준 14719: 빗물 - 구현(파이썬)

빗물 성공

14719번: 빗물

문제

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

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

입력

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

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

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

출력

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

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

 

내 코드

import sys
h,w=map(int,sys.stdin.readline().split())
arr=list(map(int,sys.stdin.readline().split()))

#h*w 배열 생성(0 초기화)
myMap=[]
for _ in range(h):
    myMap.append([0]*w)

#문제에서 주어진 블록들 생성.(블록을 1로 생성)
for i in range(w):
    for j in range(arr[i]):
        myMap[h-1-j][i]=1


for i in range(h):
    save=[]
    for j in range(w):
        if myMap[i][j]==1: #블록이면,
            save.append(j) #save에 저장.
        if len(save)==2: #save에 블록 두개가 저장되면, 물 고일 수 있음.
            for k in range(save[1]-save[0]-1): #두 블록 사이의 빈칸 개수만큼 물 고임.   
                myMap[i][save[0]+1+k]=2 #물을 2로 생성.
            save.pop(0) #두 블록중 첫 블록을 없애서 다음 블록이 올 수 있게 하기

answer=0
for x in myMap:
    answer+=x.count(2) #고인 물을 카운트
print(answer)

 

풀이 및 접근)

- 문제를 보자마자 풀이가 떠오르지 않아서 일단 주어진 크기의 배열을 생성하고, 문제에 주어진대로 블록을 세팅했다.

- 그리고 나서 물은 빈칸에 들어올 수 있으므로, 그 빈칸들 중에 물이 들어올 칸을 다른 값으로 바꾸어 그 값을 카운팅 하기로 했다.

- 그러다보니 규칙을 찾을 수 있었는데, 특정 가로 줄에서 블록~블록의 쌍이 있으면 그 사이에 무조건 물이 고일 수 있다는 것이었다.

- 예를 들어 특정 가로 줄이

블록1 ㅁ ㅁ ㅁ ㅁ 블록2 ㅁ ㅁ ㅁ 블록3 ㅁ ㅁ 블록4     형태이면,

블록1이 save에 저장되고 블록2가 save에 저장됐으면, 저 둘 사이의 네칸이 물이 고이게 처리된다. 그리고나서 이후의 블록이 더 있을 수 있으므로, save 안에 있는 두 블록중 첫번째 블록을 제거한다. 그렇게 되면 다음에 블록2~블록3의 쌍을 만들 수 있다.

- 이런 식으로 물이 고이는 칸을 체크하여 2로 마킹하면, 최종 배열에서 2의 개수를 세면 그것이 물이 고인 칸의 개수가 된다.

 

 

최적화 된 다른 풀이

import sys
h,w=map(int,sys.stdin.readline().split())
arr=list(map(int,sys.stdin.readline().split()))

answer = 0
for i in range(1,w-1): #가로축 상에서 양끝을 제외한 지점에서 물이 고일 수 있음.

    #현재 지점 기준의 왼쪽, 오른쪽에서 가장 높은 블록 높이를 저장.
    left_max=max(arr[0:i])
    right_max=max(arr[i+1:w])

    #물이 고인다면 둘 중 작은 높이에 대해서 물이 고인다.
    limit=min(left_max,right_max)

    if arr[i]<limit: #위에서 구한 limit보다 현재 지점의 블록 높이가 낮으면,
        answer+=limit-arr[i] #limit-현재 높이 만큼 물이 고일 수 있다.

print(answer)

*참고한 블로그

https://seongonion.tistory.com/115

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