이번 문제는 BFS 알고리즘을 통해 해결하였다. 문제를 보자마자 BFS 알고리즘을 통해 해결해야겠다는 생각을 했지만 공기 중과 구멍을 분간하는 법에 대한 방법이 떠오르지 않았다. 이 부분에 대해서 오랫동안 고민하다가 다른 사람의 풀이법을 보았고, 0에서 1로 가는 부분만 공기에 노출된 치즈라는 것을 알게 되었다. 생각해보니 1에서 0으로 가는 것은 구멍일 수 밖에 없었다. 이 규칙을 가지고 풀이를 작성하였다. 우선 0,0은 무조건 0이므로 탐색을 0,0부터 시작하도록 하였고, 치즈를 녹이는 과정에서 치즈의 크기까지 카운팅 하도록 하였다. 다음 탐색 치즈가 1일 경우는 공기중에 노출된 치즈이므로 0으로 바꿔주고, 카운팅 변수를 1 증가시켜줬다. 다음 탐색 치즈가 0일 경우에는 큐에 넣어주도록 하였다. 중복 확인을 막기 위해 방문 처리 리스트를 사용하였고, 모든 탐색에서 방문 처리를 하도록 하였다. bfs함수를 실행한 후에 반환된 치즈의 크기는 치즈의 크기를 모으는 리스트에 담았고, 이 리스트의 가장 마지막 변수는 0이 되므로, 인덱스-2를 접근하여 출력하였다. bfs함수를 호출할 때마다 시간 카운팅 변수를 1씩 증가시켰고, 이 시간 카운팅 변수도 출력하였다.

• n, m을 입력받는다.
• 전체 그래프를 입력받을 리스트 graph를 선언한다.
• n번 반복하며 graph를 입력받는다.
• 치즈의 크기를 담을 리스트 cheese를 선언한다.
• 시간을 카운팅할 변수 time을 -1로 선언한다.
• 동서남북을 dy, dx에 짝지어 저장한다.
• bfs함수를 선언한다.
  -> q를 deque로 선언한다.
  -> q에 (0, 0)을 넣는다.
  -> visited[0][0]을 True로 갱신한다.
  -> 치즈의 크기 카운팅 변수 cnt를 0으로 선언한다.
  -> q가 존재할 동안 반복하는 while문을 돌린다.
  --> q에서 y, x를 추출한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny를 y+dy[i]로 선언한다.
  ---> nx를 x+dx[i]로 선언한다.
  ---> 만약 ny가 0 이상, n 미만이고, nx가 0 이상, m 미만이고, visited[ny][nx]가 False일 경우,
  ----> 만약 graph[ny][nx]가 0일 경우,
  -----> visited[ny][nx]를 True로 갱신한다.
  -----> q에 (ny, nx)를 넣는다.
  ----> 만약 graph[ny][nx]가 1일 경우,
  -----> graph[ny][nx]를 0으로 갱신한다.
  -----> visited[ny][nx]를 True로 갱신한다.
  -----> cnt를 1 증가시킨다.
  -> cheese에 cnt를 넣는다.
  -> cnt를 반환한다.
• 무한 반복하는 while문을 돌린다.
  -> time을 1 증가시킨다.
  -> 방문 처리에 사용할 리스트 visited를 n*m의 리스트로 선언하고 False로 채운다.
  -> 임시 변수 cnt를 bfs()의 반환값으로 선언한다.
  -> 만약 cnt가 0일 경우, 반복을 멈춘다.
• time을 출력한다.
• cheese[-2]를 출력한다.

Code

from collections import deque
n, m=map(int, input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(int, input().split())))
cheese=[]
time=-1
dy=[0, 0, -1, 1]
dx=[1, -1, 0, 0]
def bfs():
    q=deque()
    q.append((0, 0))
    visited[0][0]=True
    cnt=0
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<n and 0<=nx<m and not visited[ny][nx]:
                if graph[ny][nx]==0:
                    visited[ny][nx]=True
                    q.append((ny, nx))
                elif graph[ny][nx]==1:
                    graph[ny][nx]=0
                    visited[ny][nx]=True
                    cnt+=1
    cheese.append(cnt)
    return cnt
while True:
    time+=1
    visited=[[False]*m for _ in range(n)]
    cnt=bfs()
    if cnt==0:
        break
print(time)
print(cheese[-2])