[백준 15972번] 물탱크 (Python3)

import sys
input = sys.stdin.readline
from collections import *

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

tank = [[H]*M for i in range(N)]

column = [[*map(int,input().split())] for i in range(N+1)]
row = [[*map(int,input().split())] for i in range(N)]

dq = [deque() for i in range(H+1)]

for y in range(N):
  if row[y][0]!=-1:
    dq[row[y][0]].append((y,0))
  if row[y][-1]!=-1:
    dq[row[y][-1]].append((y,M-1))
for x in range(M):
  if column[0][x]!=-1:
    dq[column[0][x]].append((0,x))
  if column[-1][x]!=-1:
    dq[column[-1][x]].append((N-1,x))

for h in range(H+1):
  while dq[h]:
    y,x = dq[h].pop()
    if tank[y][x] <= h:
      continue
    tank[y][x] = h
    if row[y][x]!=-1 and x:
      if row[y][x]<=h:
        dq[h].append((y,x-1))
      else:
        dq[row[y][x]].append((y,x-1))
    if row[y][x+1]!=-1 and x+1<M:
      if row[y][x+1]<=h:
        dq[h].append((y,x+1))
      else:
        dq[row[y][x+1]].append((y,x+1))
    if column[y][x]!=-1 and y:
      if column[y][x]<=h:
        dq[h].append((y-1,x))
      else:
        dq[column[y][x]].append((y-1,x))
    if column[y+1][x]!=-1 and y+1<N:
      if column[y+1][x]<=h:
        dq[h].append((y+1,x))
      else:
        dq[column[y+1][x]].append((y+1,x))

print(sum(map(sum,tank)))

BFS로 해결하였다.

수영장 사장님 [백준 15730번] 수영장 사장님 (Python3) (tistory.com) 과 사실상 완전히 똑같은 방식으로 해결할 수 있다. 수영장 사장님 문제에서는 각 좌표가 그 자체로서 벽의 역할을 했다면, 이 문제에서는 벽이 각 좌표의 4방향에 존재한다는 것이 차이점이다.

 

풀이를 설명하면,

1. 높이 0~H까지 H+1개의 deque를 만든다.

2. 가장 바깥쪽을 높이 0의 물이라고 생각하고 h=0~H까지 H+1번 BFS를 실행한다.

3. 각 좌표에서 4방향에 대해서 경계를 이루는 벽의 높이가 현재 높이 h보다 작은 경우 해당 좌표를 현재 deque에 넣고, 더 큰 경우, 해당 높이의 deque에 넣는다.

4. 물 높이의 합을 출력한다.

 

다른 사람들 풀이를 보니 우선순위 큐를 이용한 풀이가 많아보였다. 우선순위 큐를 이용한 풀이도 나쁜 방법은 아니지만 우선순위 큐의 사용으로 인해 시간복잡도가 O(NMlogNM)이 되는 반면, 내 풀이는 O(NM)으로 해결가능하다.

 

파이썬 기준, 성능에서 우선순위 큐를 이용한 다른 사람들 풀이보다 압도적으로 빠른 것을 알 수 있다.