[Gold V] 빗물 - 14719

문제 링크

성능 요약

메모리: 34092 KB, 시간: 432 ms

분류

구현, 시뮬레이션

문제 설명

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

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

입력

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

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

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

출력

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

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

풀이

아이디어

우선 width, height대로 실제 그래프를 만들고, 빗물이 떨어진다면 아래의 조건을 만족한 경우 빗물이 고일수 있으므로 그대로 구현하였다.
1. 일단 비는 내린다
2. 양쪽이 막혔는지 확인한다.
3. 만약 막히지 않는 곳이라면 그 위로부터는 쌓지 못한다.

코드

width, height = map(int, input().split())
stack = map(int, input().split())
graph = [[0]* height for _ in range(width)]
res = 0

for i, s in enumerate(stack):
    for j in range(s):
        graph[j][i] = 1

for i in range(width):
    for j in range(height):
        if graph[i][j] == 0:
            graph[i][j] = 9

    for k in range(height):
        if graph[i][k] == 9:
            try:
                w_s, w_e = graph[i][:k].index(1), graph[i][k+1:].index(1)
            except ValueError:
                graph[i][k] = -1

print(sum(graph, []).count(9))

---

회고

간만에 힐링문제였다. 요즘 PS문제를 어려운것밖에 안해서 흥미가 떨어질뻔 했는데 뇌 빼고 해도 풀리는 문제 하니 다시 재밌어졌다. 다만 위 문제 조건에서 아무리 해봐야 최종 계산이 1억을 넘지 않는다는것을 확인했고 그래서 뇌빼고 풀 수 있었던거라 숫자가 커지면 시간복잡도는 지수시간 비스무리하게 커질것으로 보인다. 또한 PS에서 count라던가 index라던가 뭐 del이라던가 이런 인스턴스들 쓰는거 별로 안좋아하는데 그런면에서는 마음에 들지 않은 코드이다.