[백준 1113번] 수영장 만들기 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]

def BFS(y,x,n):
  visited = [[0]*M for i in range(N)]
  dq = deque()
  dq.append((y,x))
  co = []
  border = []
  while dq:
    y,x = dq.popleft()
    if visited[y][x]:
      continue
    visited[y][x] = 1
    if pool[y][x] >= n:
      border.append((y,x))
      continue
    co.append((y,x))
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if not (N>y1>=0 and M>x1>=0):
        return False
      if visited[y1][x1]:
        continue
      dq.append((y1,x1))
  for y,x in co:
    waterlevel[y][x] = n
  for y,x in border:
    waterlevel[y][x] = -1
  return True    

N,M = map(int,input().split())

pool = []
for i in range(N):
  pool.append([*map(int,[*input().strip()])])

waterlevel = [[0]*M for i in range(N)]

for y in range(1,N-1):
  for x in range(1,M-1):
    if waterlevel[y][x]:
      continue
    for i in reversed(range(pool[y][x]+1,10)):
      if BFS(y,x,i):
        break
    if not waterlevel[y][x]:
      waterlevel[y][x] = -1

result = 0
for y in range(1,N-1):
  for x in range(1,M-1):
    if waterlevel[y][x] != -1:
      result += waterlevel[y][x]-pool[y][x]

print(result)

 

간단한 BFS 문제이다.

알고리즘을 요약하면,

1. 모든 지점에서 BFS를 (9-현위치높이)번 실행

2. 현 위치에서부터 높이 n 이하의 지점을 찾으며, 범위 밖으로 벗어날 경우 물이 샌다는 의미이므로 False를 return

3. 물이 안샐 경우 BFS로 찾은 모든 지점의 물의 높이를 기록

4. 모든 지점에서 물의 높이와 바닥 높이의 차이의 합 출력

 

코드 시간은 조금 오래걸렸다. 풀면서 생각한게 모든 지점에서 BFS를 하는것보다 가장 바깥에서 BFS를 하는게 나았겠다는 생각을 했다.

 

 

오늘의 교훈) 효율적으로 코드를 짜자