[백준 1113번] 수영장 만들기(파이썬)

https://www.acmicpc.net/problem/1113

1113번: 수영장 만들기

상당히 까다로웠던 문제.

문제 자체가 어려워서 많이 해매었고

구글링을 통해서 해결할 수 있었습니다.

https://injae-kim.github.io/problem_solving/2020/02/15/baekjoon-1113.html

Injae's devlog

제가 참고한 페이지입니다.

이 분은 발상을 다르게 해서 접근했는데

'물을 하나씩 채운다'가 아닌

'물을 미리 다 채우고

하나씩 빼준다'

라는 식으로 접근했습니다.

이 방법에 대해서 설명이 잘되어있으니 참고해보세요.

#백준 1113번 수영장
from collections import deque
N,M=map(int,input().split())

dx=[1,-1,0,0]
dy=[0,0,1,-1]

room=[]
for _ in range(N):
    tmp=map(int,input().rstrip())
    tmp=list(tmp)
    room.append(tmp)

mi,ma=1e9,0
for x in range(N):
    for y in range(M):
        mi=min(mi,room[x][y])
        ma=max(ma,room[x][y])
water=[[0]*M for _ in range(N)]
for x in range(1,N-1):
    for y in range(1,M-1):
        water[x][y]=ma-room[x][y]


def bfs(x,y,height):

    q=deque()
    q.append([x,y])
    visited[x][y]=True
    while q:
        x,y=q.popleft()

        water[x][y]-=1
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]
            if nx<0 or nx>=N-1 or ny<0 or ny>=M-1:
                continue
            if visited[nx][ny]==True:
                continue

            if water[nx][ny]+room[nx][ny]==height and water[nx][ny]>0:
                q.append([nx,ny])
                visited[nx][ny]=True



answer=0
#물을 꽉 채운 후 역으로 계산


for he in range(ma,mi,-1):
    visited=[[False]*M for _ in range(N)]
    for x in range(1,N-1):
        for y in range(1,M-1):
            if water[x][y]>0 and not visited[x][y]:
                for d in range(4):
                    nx=x+dx[d]
                    ny=y+dy[d]
                    if room[nx][ny]+water[nx][ny]<room[x][y]+water[x][y]:
                        bfs(x,y,he)
                        break

answer=0

for x in range(1,N-1):
    for y in range(1,M-1):
        answer+=water[x][y]

print(answer)

발상이 어려웠던 만큼

정리하기 좋은 문제입니다.

한번쯤 문제 자체를 깔끔하게 집어넣을만합니다.