백준 14719 - 빗물 (파이썬)
글 작성자: pental
https://www.acmicpc.net/problem/14719
풀이
주어진 블록 배치에서 빗물이 고이는 양을 구하는 문제이다.
문제에서는 2차원 격자를 생성해서 풀어야 하기 떄문에 다음과 같이 선언하였다.
B = [[0] * W for _ in range(H)]
블록을 채우기 위해서 다음과 같이 수행한다.
for i in range(H) :
for j in range(A[i]) :
B[H - 1 - j][i] = 1
- 각 열(i)에서 블록의 높이만큼(A[i]) 1을 채운다.
- (H - 1 - j, i) 위치를 1로 설정해서 바닥부터 쌓이도록 만든다.
빗물을 계산하기 위해서 다음과 같이 수행한다.
count = 0
for i in range(H):
for j in range(W):
if B[i][j] == 1:
continue
즉, 격자를 한 칸씩 탐색하면서 0인칸(빈공간)을 확인한다.
왼쪽 벽 확인을 위해서 다음과 같이 수행한다.
k = j
while k >= 0:
if B[i][k] == 1:
break
k -= 1
if k == -1:
continue # 왼쪽에 벽이 없으면 물이 안 고임
- 현재 위치에서 왼쪽 방향으로 이동하며 1을 찾는다.
- 왼쪽 끝까지 가도 1이 없다면 이 위치에는 빗물이 안고이므로 건너뜀
오른쪽 벽 확인을 위해서 다음과 같이 수행한다.
k = j
while k < W:
if B[i][k] == 1:
break
k += 1
if k == W:
continue # 오른쪽에 벽이 없으면 물이 안 고임
- 현재 위치에서 오른쪽 방향으로 이동하며 1을 찾는다.
- 오른쪽 끝까지 가도 1이 없다면 이 위치에는 빗물이 안고이므로 건너뛴다.
오른쪽과 왼쪽 벽이 모두 존재하면 빗물이 고이는 공간이므로 count를 증가한다.
코드
# 백준 14719 - 빗물
# 분류 : 브루트 포스
H, W = map(int, input().split())
A = list(map(int, input().split()))
B = [[0] * W for _ in range(H)]
for i in range(H) :
for j in range(A[i]) :
B[H - 1 - j][i] = 1
count = 0
for i in range(H) :
for j in range(W) :
if B[i][j] == 1 :
continue
k = j
while k >= 0 :
if B[i][k] == 1 :
break
k -= 1
if k == - 1 :
continue
k = j
while k < W :
if B[i][k] == 1 :
break
k += 1
if k == W :
continue
count += 1
print(count)
'Programming > 백준' 카테고리의 다른 글
백준 1300 - K번째 수 (파이썬) (0) | 2025.03.06 |
---|---|
백준 1303 - 전쟁 - 전투 (파이썬) (0) | 2025.03.06 |
백준 17086 - 아기 상어 2 (파이썬) (0) | 2025.03.04 |
백준 2293 - 동전 1 (파이썬) (0) | 2025.03.04 |
백준 1062 - 가르침 (파이썬) (0) | 2025.03.03 |
댓글
이 글 공유하기
다른 글
-
백준 1300 - K번째 수 (파이썬)
백준 1300 - K번째 수 (파이썬)
2025.03.06 -
백준 1303 - 전쟁 - 전투 (파이썬)
백준 1303 - 전쟁 - 전투 (파이썬)
2025.03.06 -
백준 17086 - 아기 상어 2 (파이썬)
백준 17086 - 아기 상어 2 (파이썬)
2025.03.04 -
백준 2293 - 동전 1 (파이썬)
백준 2293 - 동전 1 (파이썬)
2025.03.04