[BOJ/백준] 8982 수족관 1 파이썬

문제 링크 : https://www.acmicpc.net/problem/8982

8982번: 수족관 1

 

문제의 설명은 어렵지 않지만 생각을 좀 많이 한 문제이다.

 

문제의 핵심은 수족관에 깊이를 수정해가는 것이다.

한 구멍으로 물이 빠졌을 때의 수족관의 물의 빠진 양을 수정하는데 이를 모든 구멍에 대해서 실행해보는 것이다.

 

예를 들어 2번 구멍으로 먼저 물이 빠진다 했을 때

왼쪽 첫번째 파란 원의 물의 양은 3, 오른쪽 파란원도 3, 그 오른쪽은 2가 될 것이다.

그 다음 1번 구멍으로 물이 빠진다고 한다면 2번 구멍에서 빼낸 물의 양보다 많이 빼낼 수 있는 경우에 해당 양을 수정해 나가는 것이다.

 

문제를 풀기 위해선 전처리가 필요하다.

나는 문제의 x,y를 반대로 바꿔서 진행했다.

우선 입력으로 주어진 수조관 바닥의 두 꼭지점을 하나의 점으로 바꿨다.

깊이 x와 넓이, 시작 점 y, 해당 바닥의 길이, 그리고 물이 빠진 양이다.

그리고 맨처음과 맨마지막 점의 경우 수조관 바닥을 나타내지않기 때문에 필요가 없어서 그 사이 점들만을 이용했다.

 

그리고 구멍의 정보인데 그냥 이것 x,y만 바꿔서 넣고 첫번째 꼭지점의 y값을 기준으로 정렬했다.

정렬한 이유는 위에서 전처리한 구멍을 앞에서 부터 하나씩 돌면서 구멍인지 아닌지 체크하기 위함이다. 

 

이제 반복문을 돌리면 된다.

모든 꼭지점을 돌면서 구멍이 있는 꼭지점일 경우 이제 체크를 진행한다.

체크는 현재 점을 기준으로 왼쪽과 오른쪽으로 나눠서 진행한다.

각 방향으로 가면서 해당 점의 물이 빠진 양이 지금 빼내려는 물의 양보다 크다면 구멍보다 물이 높이가 낮은 곳이다.

 

그림에서 2번 구멍으로 물 먼저 빼고 1번 구멍으로 물을 빼려고 할때

1번 구멍 왼쪽의 점들은 모두 3만큼 물을 빼냈다. 그렇기 때문에 1번 구멍보다 높이가 낮기 때문에 물을 뺄 수가 없다.

이런 상황이 오면 더이상 확인할 필요 없이 나가면 된다.

이 다음 점들은 모두 다른 구멍에 의해 현재 구멍보다 높이가 낮아진 구멍이기 때문이다.

 

그리고 만약 해당 점의 높이가 구멍보다 낮다면 해당 기준 높이를 해당 점의 높이로 바꾸고 물을 수정된 기준 높이만큼 빼주면 된다.

 

 

설명은 조금 많이 부족한데 코드를 보면 금방 이해가 될 듯하다.

from sys import stdin

input = stdin.readline

n = int(input())
points = []
size = 0
input()
for _ in range(n//2-1):
    sy,sx = map(int, input().split())
    ey,ex = map(int, input().split())
    points.append([sx,sy,ey-sy,0])
    size += sx*(ey-sy)

input()
m = int(input())
holes = []
for _ in range(m):
    sy,sx,ey,ex = map(int, input().split())
    holes.append([sx,sy,ex,ey])

holes.sort(key=lambda x:x[1])

def solv():
    global size
    hole_idx = 0
    for idx in range(n//2-1):
        x, y, length, water = points[idx]
        if hole_idx < m and holes[hole_idx][0] == x and holes[hole_idx][1] == y:
            hole_idx += 1
            renew_water(idx,-1,x,-1)
            renew_water(idx+1, n//2, x,1)

    for idx in range(n//2-1):
        size -= points[idx][3]*points[idx][2]
    print(size)

def renew_water(start,end,h,op):
    global points

    for idx in range(start,end,op):
        if idx >= len(points):
            return
        if points[idx][3] < h:
            if points[idx][0] < h:
                h = points[idx][0]
            points[idx][3] = h
        else:
            break

solv()