[Python][백준 14719] 빗물

[백준] 빗물 (Python 풀이)

📌 문제 분석

이 문제는 2차원 세계에서 블록으로 이루어진 지형 위에 비가 내렸을 때 고이는 빗물의 총량을 구하는 문제입니다.

주어진 입력으로 각 열의 블록 높이가 주어지며, 이를 바탕으로 빗물이 얼마나 고일 수 있는지를 계산해야 합니다.

🚨 시행착오

처음에는 높이를 기반으로 2차원 배열을 생성한 후, 각 행에서 빗물이 고일 수 있는 공간을 탐색하는 방식으로 접근했습니다.

그러나, 해당 접근 방식은 불필요한 메모리 사용이 많았고, 더 효율적인 해결 방법이 존재한다는 점을 깨달았습니다.

어떻게 고쳤나요?

• 2차원 배열을 만들지 않고, 높이를 기준으로 직접 탐색하여 빗물의 양을 계산하는 방식으로 변경했습니다.
• 좌측과 우측에서 현재 높이보다 큰 블록을 찾는 방향으로 개선했습니다.

💡 해결 방안 (2차원 배열 사용)

import sys

sys.stdin = open("input.txt", "r")

H, W = map(int, input().split())
limit = list(map(int, input().split())) 
arr = [[] for _ in range(H)]
result = 0

# 2차원 배열 생성
for i in range(H):
    for j in range(W):
        if i < limit[j]:
            arr[i].append(1)
        else:
            arr[i].append(0)

# 빗물 계산
for i in range(H):
    flag = 0
    for j in range(1, W):
        if arr[i][j] == 0 and arr[i][j - 1] == 1:
            flag = j
        elif arr[i][j] == 1 and flag != 0:
            result += j - flag 
            flag = 0

print(result)

# 배열 출력
for ar in arr:
    print(ar)

💡 해결 방안 (1차원 리스트 사용, 더 효율적인 방법)

import sys

sys.stdin = open("input.txt", "r")

H, W = map(int, input().split())
limit = list(map(int, input().split()))

result = 0

# 각 위치에서 좌우의 최대 높이를 구하여 빗물이 고이는 양을 계산
left_max = [0] * W
right_max = [0] * W

left_max[0] = limit[0]
for i in range(1, W):
    left_max[i] = max(left_max[i - 1], limit[i])

right_max[W - 1] = limit[W - 1]
for i in range(W - 2, -1, -1):
    right_max[i] = max(right_max[i + 1], limit[i])

for i in range(W):
    result += max(0, min(left_max[i], right_max[i]) - limit[i])

print(result)

🎯 이 문제의 핵심 포인트

• 높이를 기반으로 물이 고일 수 있는 공간을 계산하는 방법
• 2차원 배열을 활용한 접근법과 그 한계
• 1차원 리스트를 활용한 효율적인 빗물 계산 방식

📝 예제로 이해하기

예제 입력

4 4
3 0 1 4

예제 출력

5

설명

• 첫 번째 열(높이 3)과 마지막 열(높이 4) 사이에 빗물이 고이는 구조가 됩니다.

✨ 이번 문제를 통해 배운 점

• 2차원 배열을 직접 생성하는 방식의 비효율성을 체감
• 1차원 리스트와 포인터를 활용한 효율적인 방법 고려
• 배열 탐색 방식 최적화의 필요성

🔍 코드 설명

• 2차원 배열 접근법: 블록이 있는 위치를 1, 없는 위치를 0으로 저장한 후 행별로 탐색하여 빗물 계산
• 1차원 리스트 접근법: 왼쪽과 오른쪽에서 현재 위치보다 높은 블록을 찾아 최소 높이만큼 빗물이 고일 수 있도록 계산
• 출력: 중간 과정과 최종 결과를 출력하여 디버깅 및 확인

이 문제를 해결하며 빗물 계산 알고리즘의 기본 개념을 익히고, 더 최적화된 풀이 방법을 고민할 수 있었습니다.