이번 문제는 깊이우선탐색을 통해 해결하였다. 처음에는 치즈인 좌표에서 공기와 접촉한 면이 몇개인지 판단하고 지우는 방식으로 접근하였다. 그러나 이 경우, 하나의 좌표가 지워지면 다른 좌표에 영향을 줘서 결국 다른 방식으로 처리되었다. 그러던 중에 반대로 생각해보기로 하였다.

값이 0, 즉 좌표가 가리키는 값이 공기인 경우에는 방문처리를 한 후에 재귀호출하고, 가리키는 값이 치즈인 경우에는 값을 1 증가시킨다. 치즈의 값이 3 이상일 경우 공기와 닿는 면이 2개 이상이 된다. 한번의 깊이우선탐색을 진행 후에 3이상인 치즈를 0으로 바꿔주는 연산을 진행하게 되면 문제에서 요구하는 조건대로 치즈가 녹게 된다.

위의 그림은 예제에 대한 첫번째 깊이우선 탐색 후의 치즈이다. 3 이상이 된 츠즈들은 모두 0으로 갱신되게 된다.

• 재귀 제한을 늘려준다.
• dfs함수를 y, x를 인자로 갖도록 선언한다.
  -> 4가지 방향에 대한 정보를 dy, dx 리스트에 짝지어 저장한다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> ny를 y+dy[i]로 저장한다.
  --> nx를 x+dx[i]로 저장한다.
  --> 만약 ny, nx가 0보다 크거나 같고, ny가 n보다 작고, nx가 m보다 작고, visited[ny][nx]가 False일 경우,
  ---> 만약 cheese[ny][nx]가 0이 아닐 경우, cheese[ny][nx]를 1 증가시킨다.
  ---> 그 외에는 visited[ny][nx]를 True로 갱신하고 dfs(ny, nx)를 재귀호출한다.
• n, m을 입력받는다.
• 치즈에 대한 정보를 담을 리스트 cheese를 선언한다.
• n번 반복하는 for문을 돌린다.
  -> cheese를 입력받는다.
• 정답을 저장할 변수 answer를 0으로 선언한다.
• 계속 반복하는 while문을 돌린다.
  -> 만약 cheese가 n*m의 0으로 이뤄진 리스트일 경우,
  --> answer를 출력한다.
  --> while문을 탈출한다.
  -> 방문처리에 사용할 리스트 visited를 n*m의 False로 이뤄진 리스트로 선언한다.
  -> visited[0][0]을 True로 갱신한다.
  -> dfs(0, 0)을 호출한다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> m번 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 cheese[i][j]가 3 이상일 경우, cheese[i][j]를 0으로 갱신한다. (2개 이상의 변이 공기와 접촉된 치즈)
  ---> 만약 cheese[i][j]가 0보다 클 경우, cheese[i][j]를 1로 갱신한다. ( 2개 미만의 변이 공기와 접촉된 치즈)
  -> answer를 1 증가시킨다.

Code

import sys
sys.setrecursionlimit(10**9)
def dfs(y, x):
    dy=[0, 0, -1, 1]
    dx=[1, -1, 0, 0]
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny>=0 and nx>=0 and ny<n and nx<m and visited[ny][nx]==False:
            if cheese[ny][nx]!=0:
                cheese[ny][nx]+=1
            else:
                visited[ny][nx]=True
                dfs(ny, nx)

n, m=map(int, input().split())
cheese=[]
for _ in range(n):
    cheese.append(list(map(int, input().split())))
answer=0
while True:
    if cheese==[[0]*m for _ in range(n)]:
        print(answer)
        break
    visited=[[False]*m for _ in range(n)]
    visited[0][0]=True
    dfs(0, 0)
    for i in range(n):
        for j in range(m):
            if cheese[i][j]>=3:
                cheese[i][j]=0
            elif cheese[i][j]>0:
                cheese[i][j]=1
    answer+=1