백준(BOJ) 1113 수영장 만들기(Python)

문제 내용

 

BFS 문제.

가장 먼저 물을 채울 시작점을 구해야한다고 생각했다.

물을 채울 수 있다는 근거는, 칸의 상하좌우 중 현재 칸의 높이보다 높은 칸이 존재하는 것이라고 생각했다.

그렇게 칸을 정하고 나면 상하좌우 중 가장 높은 높이부터 가장 낮은 높이까지 물을 채워본다. 편의상 물의 높이를 w라 하겠다.

w보다 칸의 높이가 더 낮다면 queue에 칸의 좌표를 push하는 방식으로 BFS를 진행했다.

만약 BFS를 진행하다 리스트 범위를 벗어나는 좌표가 나타나면 이는 물이 넘치는 것이므로 BFS를 중단한다.

그렇지 않고 끝났다면 현재 w는 그 칸에서 시작해 채울 수 있는 가장 높은 물의 높이일 것이므로, BFS를 하며 계산한 수영장의 부피를 ans에 더한다.

만약 물을 채우는 데에 성공했다면 모든 칸의 높이를 BFS 이후로 갱신해준다. 이는 deepcopy를 이용해 구현했다. BFS를 돌 때의 높이를 따로 구하다 마지막에 덮어씌우는 것이다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,m=map(int,input().split())
L=[list(map(int,input())) for i in range(n)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
ans=0
for i in range(n):
    for j in range(m):
        flag=0
        p=L[i][j]
        a=10
        b=0
        for k in range(4):
            nx=i+dx[k]
            ny=j+dy[k]
            if 0<=nx<n and 0<=ny<m:
                if L[nx][ny]>p:
                    flag=1
                    a=max(a,L[nx][ny])
                    b=min(b,L[nx][ny])
        if flag:
            for w in range(a,b-1,-1):
                flag3=0
                if L[i][j]<w:
                    visited=[[0 for _ in range(m)] for _ in range(n)]
                    X=copy.deepcopy(L)
                    queue=deque()
                    queue.append([i,j])
                    visited[i][j]=1
                    c=0
                    while queue:
                        flag2=0
                        x,y=queue.popleft()
                        c+=w-X[x][y]
                        X[x][y]=w
                        for k in range(4):
                            nx=x+dx[k]
                            ny=y+dy[k]
                            if 0<=nx<n and 0<=ny<m:
                                if X[nx][ny]<w and not visited[nx][ny]:
                                    queue.append([nx,ny])
                                    visited[nx][ny]=1
                            else:
                                flag2=1
                                flag3=1
                                break
                        if flag2:
                            c=0
                            break
                    if c:
                        L=copy.deepcopy(X)
                    ans+=c
                if not flag3:
                    break
print(ans)

 

처음에는 채울 물의 높이를 상하좌우 중 현재 칸보다 크면서 가장 작은 값으로 선택했는데, 틀렸는데 반례를 찾지 못해 좀 애먹었다.

python으로 제출하니 시간 초과가 터졌고, pypy로 제출해서 통과를 받았다.

다른 사람들이 푼 것을 보니 처음부터 물의 높이만 조절해서 BFS를 돌려서 풀 수 있는 것을 확인했다.

확실히 내 코드보다 훨씬 효율적인 것 같다.

내 코드는 되게 비효율적인 것 같다.

아직 한참 멀었다.