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배나 감소하는 효과를 가져왔다.... (대체 전의 알고리즘은 얼마나 비효율적이었던건지)
오늘의 교훈) 시간복잡도를 줄이자