코드

import sys
input = sys.stdin.readline

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

graph = [list(map(int,input().split(" "))) for _ in range(N)]


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

from collections import deque


def bfs(x,y):

    Q = deque([(x,y)])
    
    while Q:
        x,y = Q.popleft()
        visited[x][y] = True    

        sub_cnt = 0
        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:
                if graph[nx][ny] == 0:
                    sub_cnt += 1
                if graph[nx][ny] != 0 :
                    Q.append([nx,ny])
                    visited[nx][ny] = True
        if graph[x][y]-sub_cnt < 0:
            graph[x][y] = 0
        else:
            graph[x][y] -= sub_cnt

cnt = 0
while True:
    
    visited = [[False for _ in range(M)] for _ in range(N)]
    temp = 0

    for i in range(N):
        for j in range(M):
            if graph[i][j] > 0 and visited[i][j] == False:
                bfs(i,j)
                temp+=1
                if temp >= 2:
                    break

        if temp>=2:
            break
    if temp == 0:
        print(0)
        break

    if temp >= 2:
        print(cnt)
        break
    cnt += 1

풀이

• 우선 BFS를 통해 빙산의 상하좌우 중에 바다인 (0) 개수를 구한다.
• 빙산 개수만큼 빼주고, 뺀 값이 음수이면 0으로 저장한다.
• 빙산인 값들과 방문하지 않은 값들만 BFS를 진행.
  - BFS를 돌고나면 temp에 1을 더해서 덩어리의 개수를 구하도록 한다.
  • 만약 temp가 2 이상이라면, 덩어리가 하나 더 있어서 또 bfs를 돌게 된다. -> 덩어리가 나뉘어졌다.
• temp가 0이라는 것은 마지막에 한번에 다 녹아서 결국은 덩어리가 끝까지 안 나뉘고 없어질 때를 말하므로 0을 출력하게 한다.