problem-2573

과정
1. check 함수를 통해 이 빙산이 2개 이상으로 분리되었는지 확인한다.(bfs)
2. is_finished 함수를 통해 모든 빙하가 녹았는지 확인한다.
3. 기존 arr를 deep copy로 temp_arr로 복사해놓는다.
-> 순차적으로 녹는게 아니라 한번에 녹기 때문에, temp_arr로 주위 바다 수를 구하고, arr에다가 적용 한다.
4. 분리되었거나 모든 빙하가 녹았을 때 반복문을 종료한다.

4-1. check()가 true로 반환될 경우 -> 빙하가 분리됨 -> answer그대로 출력
4-2. check()는 false인데 is_finished()가 true일 경우 -> 분리되지않고 녹음 -> answer=0
4-3. 반복문을 한 번 돌 때마다 answer+=1
4-4. 미리 복사해놓은 temp_arr[nx][ny]가 바다면 num(주위바다수)+=1, arr[i][j] = max(arr[i][j]-num,0)
4-5. 마지막엔 temp_arr에 arr를 deepcopy하여 녹은게 반영되도록 함.

from collections import deque
import copy
import sys
input=sys.stdin.readline
def check(arr):
    visited=[[False]*m for i in range(n)]
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    ans=0
    for i in range(n):
        if ans>1:
            break
        for j in range(m):
            if ans>1:
                break
            if arr[i][j]!=0 and not visited[i][j]:
                ans+=1
                que=deque([(i,j)])
                visited[i][j]=True
                while que:
                    x,y=que.popleft()
                    for k in range(4):
                        nx,ny=x+dx[k],y+dy[k]
                        if nx>=0 and ny>=0 and nx<n and ny<m and not visited[nx][ny] and arr[nx][ny]!=0:
                            visited[nx][ny]=True
                            que.append((nx,ny))

    if ans>1:
        return True
    else:
        return False

def is_finished(arr):
    
    for i in range(n):
        for j in range(m):
            if arr[i][j]!=0:
                return False
    return True


n,m=map(int,input().split())
arr=[]

for i in range(n):
    arr.append(list(map(int,input().split())))

answer=0

while True:
    temp_arr=copy.deepcopy(arr)
    if is_finished(arr):
        answer=0
        break
    if check(arr):
        break
    answer+=1
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]

    for i in range(n):
        for j in range(m):
            if temp_arr[i][j]!=0:
                num=0
                for k in range(4):
                    nx,ny=i+dx[k],j+dy[k]
                    if nx>=0 and ny>=0 and nx<n and ny<m and temp_arr[nx][ny]==0:
                        num+=1
                arr[i][j]=max(arr[i][j]-num,0)
    temp_arr=copy.deepcopy(arr)

print(answer)

time:40분