[파이썬] 백준 14719 : 빗물 (골드5)

[파이썬] 백준 14719 : 빗물 (골드5)

• https://www.acmicpc.net/problem/빗물

---

풀이

방향성 생각

• 왼쪽 벽이 아닌 높이에서 출발해서 같은 높이의 벽을 세워준다.
• 마찬가지로 오른쪽 벽이 아닌 높이에서 출발해서 같은 높이의 벽을 세워준다.
• 그 이상의 높이들은 비가 안오므로 그냥 1로 처리해주기
• 이후 BFS 진행해서 남은 영역 넓이 구하기
• 나는 그냥 입력받기 쉽게 그냥 회전시켜서 풀었다.

 

---

파이썬

from collections import deque
import sys

input = lambda : sys.stdin.readline().rstrip()
inside = lambda x,y : 0<=x<W and 0<=y<H
dire = [(1,0),(0,1),(-1,0),(0,-1)]

def bfs(sx,sy):

    Q = deque([(sx,sy)])
    while Q:
        x,y = Q.popleft()

        for dx,dy in dire:
            nx,ny = x+dx, y+dy

            if inside(nx,ny) and not V[ny][nx] and arr[ny][nx]:
                V[ny][nx] = True
                Q.append((nx,ny))

for _ in range(int(input())):
    W,H,K = map(int,input().split())

    arr = [[0]*W for _ in range(H)]
    for _ in range(K):
        x,y = map(int,input().split())
        arr[y][x] = 1

    V = [[False]*W for _ in range(H)]
    answer = 0
    for i in range(H):
        for j in range(W):
            if arr[i][j] and not V[i][j]:
                bfs(j,i)
                answer += 1

    print(answer)

• 테케 받아서 BFS 돌리기

---

import sys

input = sys.stdin.readline

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

stack = []
water = 0

for i in range(W):
    while stack and blocks[stack[-1]] < blocks[i]:  # 현재 블록이 스택의 top보다 높은 경우
        bottom = stack.pop()

        if not stack:  # 스택이 비면 더 이상 담을 수 없음
            break

        left = stack[-1]  # 왼쪽 벽
        height = min(blocks[left], blocks[i]) - blocks[bottom]  # 물 높이 계산
        width = i - left - 1  # 물이 고이는 너비

        water += height * width  # 물 저장량 추가

    stack.append(i)  # 현재 블록을 스택에 추가

print(water)

• 스택 풀이도 있다 해서 지피티 돌려봤음

---

코멘트

• 스택이랑 그리디 좀 밀어야할듯... 풀이 감이 잘 안잡힘