2573

풀이1

1. 1년후 녹는 빙산을 고르기 위해 동서남북 인덱스 배열과 빙산 배열을 비교해가며 인접한 0의 갯수만큼 빙산의 숫자를 줄인다
2. 1년씩 늘어갈때마다 bfs를 하여 인접한 위치에 빙산이 없을때를 구해본다. 배열 전체를 bfs탐색을 하며 도는데 첫번째 큐가 들어간 후 탐색 중에 큐가 들어가는 것을 제외하고 큐가 비어있을 때 나머지 빙산 배열을 돌며 다시 큐에 들어갈 빙산 인덱스가 있다면 떨어져 있는 빙산이 두개 이상이므로 그 bfs를 하고 있는 년도수가 정답이다.
3. 각 작업을 시작하기 전에 빙산 배열을 한 번 돌고 0이 없다면 0을 출력하는 조건을 만든다.

from collections import deque

n, m = map(int, input().split())

arr = []
for i in range(n):
  data = list(map(int, input().split()))
  arr.append(data)

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x, y):
  queue = deque()
  queue.append((x,y))
  visit = []
  visit.append((x,y))

  while queue:
    x, y = queue.popleft()
    for q in range(4):
      if arr[x][y] != 0:
        nx = x + dx[q]
        ny = y + dy[q]
                  
        if arr[nx][ny] == 0:
          continue
        if (nx,ny) in visit:
          continue
                    
        visit.append((nx,ny))
        queue.append((nx,ny))
          
res = 0
while True:
  check = 0
  for i in range(1, n-1):
    check += sum(arr[i])
  if check == 0:
    res = 0
    break

  visit = deque()
  for i in range(1, n-1):
    for j in range(1, m-1):
      if arr[i][j] != 0:
        visit.append((i,j))
        for q in range(4):
          if arr[i][j] != 0:
            nx = i + dx[q]
            ny = j + dy[q]
            
            if arr[nx][ny] == 0:
              if (nx,ny) not in visit:
                arr[i][j] -= 1

  x,y = visit.popleft()
  res += 1
  if bfs(x, y):
    break
  
  check = 0
  for i in range(1, n-1):
    check += sum(arr[i])
  if check == 0:
    res = 0
    break
    
print(res)