풀이

핵심은 치즈가 아닌 공기 기준 탐색.

1. 0과 1로 이루어진 graph에서 0인 부분만 탐색을 해보자.
2. 외부공기와 맞닿아 있는 치즈 벽 부분만 1번의 탐색과정에서 (nx,ny) 로 접근 가능하다.
   2-1. 외부공기에서 두번이나 접근 가능한 치즈들은 1시간 뒤에 사라지게 되는 치즈들이다.
3. 자연스럽게 두번째 조건인 치즈 벽 속에 숨어 있는 치즈들은 외부 공기에서 안전하다는 것을 만족한다. (치즈로 쌓여있기 때문에 그래프 접근이 불가능하기 때문이다)

BFS로 구현할 수 있다.

# 2638 치즈
from collections import deque
N,M=map(int,input().split())
graph=[list(map(int,input().split()))for _ in range(N)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

def BFS(graph,visited,x,y):
    queue=deque([(x,y)])
    visited[x][y]=1
    while queue:
        curx,cury=queue.popleft()

        for idx in range(4):
            nx=dx[idx]+curx
            ny=dy[idx]+cury

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue


			# 다음 좌표가 공기이고 방문하지 않은 상태라면 방문처리를 해줌
            if graph[nx][ny]==0 and visited[nx][ny]==0:
                visited[nx][ny]=1
                queue.append((nx,ny))
			# 다음 좌표가 치즈라면 방문은 하지 않고, 공기로 부터 몇번 접근 가능한지 count해줌
            if graph[nx][ny]==1:
                visited[nx][ny]=visited[nx][ny]+1


ans=0
while True:
    still=False
    visited=[[0]*M for _ in range(N)]

    BFS(graph,visited,0,0)
    # 2회 이상 다음좌표로 지목된 치즈 즉, 2면 이상 공기랑 닿은 치즈는 바로 0으로 변환
    for i in range(N):
        for j in range(M):
            if graph[i][j]==1 and visited[i][j]>=2:
                graph[i][j]=0

	# 1시간이 지났다는 것을 의미 (BFS이후 count해야함)
    ans+=1

	# graph를 선회하며 1이 남아있다면 아직 사라질 치즈가 남은 것.
    for i in range(N):
        for j in range(M):
            if graph[i][j]==1:
                still=True
    if still:
        continue
    else:
        break
print(ans)