과정
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분
