첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 땅의 높이가 주어진다. 높이는 1보다 크거나 같고, 9보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
입력 예시
3 5
16661
61116
16661
출력 예시
15
풀이
그래프 탐색을 진행하되, 다음과 같은 규칙을 적용해보자.
시작 시점의 높이보다 작거나 같은 높이만 방문하도록 한다.
만약 더 높은 높이의 좌표를 만난다면, 그 좌표는 벽이다. 벽 좌표의 높이를 저장한다. 모든 벽 좌표에 대해 최소 높이를 저장하는 것이 목표이다.
만약 유효 좌표를 벗어났다면, 시작 좌표를 포함한 모든 좌표는 바깥 공간과 맞닿아있다는 것을 의미한다. 따라서 탐색을 중지한다.
위에서 탐색을 중지하지 않은 채 모든 방문 가능한 좌표를 방문했다면, 앞서 최소 높이의 벽 좌표를 떠올려보자. 즉 방문했던 모든 좌표들은 최소 벽 높이보다 작으므로, 그 높이의 차만큼 물을 채울 수 있다. 모든 방문 좌표를 최소 벽 높이로 설정하고, 그 차를 최종 결과값에 더해 준다.
모든 좌표에 대해 위 탐색을 시행하면 된다.
풀이 코드
from collections import deque
import sys
input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
N, M = map(int, input().split())
map_list = [list(map(int, input().strip())) for _ inrange(N)]
result = 0defbfs(x, y) :
q = deque([(x, y)])
init_val = map_list[y][x]
min_border = 10
result = set()
result.add((x, y))
while q :
x, y = q.popleft()
for k inrange(4) :
ax, ay = x + dx[k], y + dy[k]
ifnot (-1 < ax < M and -1 < ay < N) :
return0, set()
if map_list[ay][ax] <= init_val and (ax, ay) notin result :
result.add((ax, ay))
q.append((ax, ay))
elif map_list[ay][ax] > init_val :
min_border = min(min_border, map_list[ay][ax])
return min_border, result
deffill(val, coord_set) :
global result
for x, y in coord_set :
result += val - map_list[y][x]
map_list[y][x] = val
for i inrange(N) :
for j inrange(M) :
val, coord_set = bfs(j, i)
if coord_set :
fill(val, coord_set)
print(result)