https://www.acmicpc.net/problem/2573

• 빙산을 녹이고, 녹인 결과를 다시 갱신하는 함수
• 갱신된 빙산 배열의 군집 개수를 파악하는 함수
• 시뮬레이션
  • 군집의 개수가 2개가 되는 year 찾기
  • year 프린트

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
queue = deque() # 아직 녹지 않은 빙산

for i in range(n):
	for j in range(m):
		if arr[i][j] > 0: # 빙산이 존재하면
			queue.append((x, y)) 

def melt(): 
	melting = { }
	
	for _ in range(len(queue)):
		count = 0 # 바다의 개수
		x, y = queue.popLeft()
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		
		for dx, dy in directions:
			nx = dx + x
			ny = dy + y
			if 0 <= nx < n and 0<= ny < m and arr[nx][ny] == 0:
				count += 1
			
		new_height = max(arr[x][y] - count, 0)
		melting[(x, y)] = new_height
		
		if new_height > 0:
			queue.appned((x, y))
	
	for (x, y), height in melting.itmes():
		arr[x][y] = height

def ice_chunks():
	if not queue:
		return 0
		
	visited = [[False] * m for _ in range(n)]
	chunks = 0
	
	def dfs(x, y):
		visited[x][y]	= True
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		
		for dx, dy in directions:
			nx = dx + x
			ny = dy + y
			if 0 <= nx < n and 0<= ny < m and arr[nx][ny] != 0 and not visited[nx][ny]:
				dfs(nx, ny)
				
   for (x, y) in queue:
			if arr[x][y] != 0 and not visited[x][y]:
				dfs(x, y)
				chunks+=1
	
	return chunks

year = 0
while True:
    ice_chunks = count_ice_chunks()
    
    if ice_chunks >= 2:  # 빙산이 분리된 경우
        print(year)
        break
    if ice_chunks == 0:  # 빙산이 모두 녹은 경우
        print(0)
        break
        
    melt()
    year += 1

import sys
sys.setrecursionlimit(10000) 
from collections import deque

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
queue = deque()

# queue에 빙산의 좌표 입력
for i in range(n):
    for j in range(m):
        if arr[i][j] != 0:
            queue.append((i, j))

def melt():
    melting = {}  # 각 빙산이 녹는 양을 저장
    length = len(queue)
    
    for _ in range(length):
        x, y = queue.popleft()
        height = arr[x][y]
        count = 0  # 주변 바다 수
        
        for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == 0:
                count += 1
                
        new_height = max(0, height - count)
        melting[(x, y)] = new_height
        if new_height > 0:
            queue.append((x, y))
            
    # 한번에 녹이기
    for (x, y), height in melting.items():
        arr[x][y] = height

def count_ice_chunks():
    if not queue:  # 빙산이 모두 녹은 경우
        return 0
        
    visited = [[False] * m for _ in range(n)]
    chunks = 0
    
    def dfs(x, y):
        visited[x][y] = True
        for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] > 0 and not visited[nx][ny]:
                dfs(nx, ny)
    
    # 모든 빙산에 대해 덩어리 개수 세기
    for (x, y) in queue:
        if arr[x][y] != 0 and not visited[x][y]:
            dfs(x, y)
            chunks+=1
    
    return chunks

year = 0
while True:
    ice_chunks = count_ice_chunks()
    
    if ice_chunks >= 2:  # 빙산이 분리된 경우
        print(year)
        break
    if ice_chunks == 0:  # 빙산이 모두 녹은 경우
        print(0)
        break
        
    melt()
    year += 1