[14719] 빗물

😲 문제

출처
2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

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

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

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

입력
4 4
3 0 1 4

출력
5

❗️ 문제 재정의

문제 설명
1. 가로와 세로가 주어진다.
2. 가로의 수만큼 입력이 주어진다. 각 숫자는 해당 열의 높이를 의미한다.
3. 바닥은 항상 막혀있다.

음 문제는 다시 3단계로 이루어진다.
1. 주어진 높이만큼 블록 쌓기
2. 블록과 블록 사이에 빗물이 내릴 수 있는지 탐색하기
3. 빗물의 수를 세기

블록은 1로 놓고 빗물이 들어갈 수 있는 공간은 0으로 놓는다. 빗물이 채워지는 공간은 2로 놓는다.

✔ 계획 수립

1. 입력높이 h+1와 입력 너비 w로 0으로 채워진 배열 만들고 바닥은 1로 초기화
2. 입력 받은 열에 해당하는 블록으로 아래부터 높이 쌓기
   블록은 1 블록이 아닌 곳은 0으로 설정
3. 0이 2로 바뀔 수 있는가를 검사
   1. 조건1. 양 옆이 벽인가?
      1. 해당 줄의 첫번째 1을 찾기
      2. 해당 줄의 마지막 1을 찾기
   2. 조건2. 벽 사이에 공간이 있는가?
4. 2에 해당하는 조건을 만족하는 0을 2로 변경하면서 2의 수를 +1한다.
5. 2의 개수를 출력한다.

👨🏻‍💻 문제 풀이

h, w = map(int, input().split())
block_hs = list(map(int, input().split()))
graph = [[0]*(w) for _ in range(h+1)]
graph[-1] = [1] * w # 바닥은 모조리 벽임.

for i in range(len(block_hs)):
    for j in range(h-1,h-block_hs[i]-1,-1):
        graph[j][i] = 1
        
cnt = 0
for i, floor in enumerate(graph[:-1]):
    # 첫 번째와 마지막 1의 위치 찾기
    idx1 = -1
    idx2 = -1
    for j, val in enumerate(floor):
        if val == 1:
            if idx1 == -1:
                idx1 = j  # 첫 번째 1의 위치
            idx2 = j  # 마지막 1의 위치 (계속 업데이트)

    # 1 사이의 0을 모두 2로 바꾸기
    if idx1 != -1 and idx2 != -1 and idx1 != idx2:
        for j in range(idx1, idx2 + 1):
            if floor[j] == 0:
                graph[i][j] = 2
                cnt += 1
print(cnt)

😅 회고

같은 구현 문제더라도 그래프가 나오면 쉬워진다..
다른 구현 문제를 더 연습해야겠다.

처음에 find를 통해 1의 위치를 찾았는데 문자열만 find가 되는걸 깜빡했었다.
index를 사용하는 방법도 있겠지만 에러처리가 귀찮고 index 또한 두 번해야하기에 2중 for문을 통해 1의 위치를 탐색했다.