[백준 15730번] 수영장 사장님 (Python3)

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

def BFS():
  visited = [[0]*(M+2) for i in range(N+2)]
  dqlist[0].append((0,0))
  for n in range(10001):
    while dqlist[n]:
      y,x = dqlist[n].popleft()
      if visited[y][x]:
        continue
      visited[y][x] = 1
      waterlevel[y][x] = n
      for i in range(4):
        y1,x1 = y+dy[i],x+dx[i]
        if N+2>y1>=0 and M+2>x1>=0:
          if visited[y1][x1]:
            continue
          if pool[y1][x1] <= n:
            dqlist[n].append((y1,x1))
          else:
            dqlist[pool[y1][x1]].append((y1,x1)) 

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

data = []
for i in range(N):
  data.append([*map(int,input().split())])
  
pool = [[0]*(M+2) for i in range(N+2)]
for i in range(N):
  for j in range(M):
    pool[i+1][j+1] = data[i][j]

waterlevel = [[0]*(M+2) for i in range(N+2)]
dqlist = [deque() for i in range(10001)]

BFS()

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

print(result)

수영장 만들기 [백준 1113번] 수영장 만들기 (Python3) (tistory.com) 와 거의 유사한 문제인데 높이의 개수만 달라졌다.

 

전에 수영장 만들기 문제를 풀면서 내 코드가 너무 오래 걸려서 가장 바깥에서부터 했으면 좋았겠다고 생각했는데, 그걸 실행할 수 있는 좋은 문제였다.

 

 

알고리즘을 요약하면,

1. 배열을 N*M 크기로 만드는 것이 아니라 가장 바깥줄에 0으로 이루어진 테두리를 추가하여 (N+2)*(M+2)의 크기로 만들어준다.

2. dqlist를 만들어 모든 높이 (10000까지) 에 대한 deque를 만든다.

3. BFS를 n=0 ~ n=1000까지 10001번 실행한다. 초기지점은 0,0으로 잡는다.

4. BFS를 하면서 현재 높이보다 작거나 같은 높이를 만나면 현재 높이의 deque에 추가, 더 큰 값을 만나면 해당 높이의 dqlist에 넣는다.

5. waterlevel 배열에 현재 높이를 기록한다.

6. waterlevel - pool의 차이의 합을 결과로 출력한다.

 

해당 알고리즘으로 푸니 백준 1113번 수영장 만들기 문제에 비해서 N,M의 범위는 2배로 H의 범위는 1000배로 데이터의 크기가 4000배나 증가했음에도 불구하고 오히려 처리속도는 3264ms >> 88ms로 40배나 감소하는 효과를 가져왔다.... (대체 전의 알고리즘은 얼마나 비효율적이었던건지)

 

 

오늘의 교훈) 시간복잡도를 줄이자