코드

from collections import deque


N,M = map(int,input().split(" "))

graph = []

cheeze = 0
for i in range(N):
    graph.append(list(map(int,input().split(" "))))

for i in range(N):    
    cheeze += sum(graph[i])


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



def BFS():
    melt = []
    global count
    Q = deque()

    Q.append([0,0])

    while Q:
        x,y = Q.popleft()

        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<M and visited[nx][ny] == False:
                visited[nx][ny] = True
                if graph[nx][ny] == 0:
                    Q.append([nx,ny])

                if graph[nx][ny] == 1:
                    melt.append([nx,ny])

    for x,y in melt:
        graph[x][y] = 0
    count += 1

    return len(melt)

count = 0

remained = []
while 1:

    visited = [[False for _ in range(M)] for _ in range(N)]

    melted = BFS()

    cheeze = cheeze - melted

    if cheeze == 0:
        print(count)
        print(melted)
        break

풀이

• 겉을 훑어야 하는 지점에 대한 생각.
• 결국은 0인 노드는 Q에 넣어서 이동할 수 있게끔 하고, 노드가 1이라면 녹아야 할 겉의 치즈이므로 melt라는 곳에 저장
• 1은 Q에 넣지 않아야 한다. 더 파고들지 않기 위해.
• 한번에 melt 해야하므로 저장하였다가 한번에 0으로 저장.