2638번 치즈 G4

치즈가 주어지고 공기에 접촉된 치즈가 차례로 녹아 없어진다.

치즈 내부의 공간은 공기가 아니다.

공기에 접촉된 면이 2개 이상이어야 녹는다.

처음에는 우선 치즈와 치즈 내부 공간을 제외한 공기 부분을 모두 찾아 2로 다시 표시해줬다.

0은 진공(?)상태, 1은 치즈, 2는 공기

최대 규모가 100x100으로 작아서 그냥 반복해서 모든 부분을 탐색했다.

처음부터 끝까지 훑어보면서 녹아 없어지는 치즈들의 위치를 기억했다가 한꺼번에 2로 바꾸어준다.

그 과정에서 진공 상태였던 곳이 공기와 닿는지 확인하고 만약 그런 부분이 있다면

그 지점부터 bfs를 통해 공기로 바꾸어 주었다.

처음에 녹여야하는 치즈의 개수를 세어놓고, 모두 놓이면 끝나도록 했다.

from sys import stdin
from collections import deque

#처음 탐색으로 공기 부분을 체크
#탐색을 반복하면서 녹을 치즈을 찾고 녹임
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def air(start):
    global cheese
    q = deque()
    q.append(start)
    cheese[start[0]][start[1]] = 2
    #2 : 공기
    while q:
        now = q.popleft()
        for i in range(4):
            nx = now[0]+dx[i]
            ny = now[1]+dy[i]
            if 0<=nx<n and 0<=ny<m and cheese[nx][ny] == 0:
                q.append((nx,ny))
                cheese[nx][ny] = 2
    
def findcheese():
    cheese_cnt = 0
    for i in range(n):
        for j in range(m):
            if cheese[i][j] == 1:
                cheese_cnt+=1
    return cheese_cnt
    
def melt(cheese_cnt):
    global cheese
    melt_time = 0
    melt_cheese = 0
    
    while melt_cheese<cheese_cnt:
        melt_pos = deque()
        new_air = deque()
        for i in range(n):
            for j in range(m):
                if cheese[i][j] == 1:
                    air_cnt = 0
                    for k in range(4):
                        if cheese[i+dx[k]][j+dy[k]] == 2:
                            air_cnt+=1
                    if air_cnt > 1:
                        melt_pos.append((i,j))
                        for k in range(4):
                            if cheese[i+dx[k]][j+dy[k]] == 0:
                                new_air.append((i+dx[k],j+dy[k]))
        for pos in melt_pos:
            if cheese[pos[0]][pos[1]] == 1:
                cheese[pos[0]][pos[1]] = 2
                melt_cheese+=1
        for new in new_air:
            air(new)   
        melt_time+=1  
        
    return melt_time
    

n, m = map(int, stdin.readline().split())
cheese = [list(map(int, stdin.readline().split())) for i in range(n)]

air((0,0))
cheese_cnt = findcheese()
result = melt(cheese_cnt)
print(result)