백준_9466_텀프로젝트

import sys
sys.stdin = open("20220717_백준_25736_빙산.txt", "r")
from copy import deepcopy
from collections import deque
input = sys.stdin.readline

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


# 빙산 주변 바다의 개수 세기
def count_ocean(x, y):
    count = 0

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m and temp_board[nx][ny] == 0:
            count += 1

    return count


# BFS로 빙산 덩어리 개수 세기
def count_iceberg(start_x, start_y):
    q = deque()
    q.append((start_x, start_y))
    visited[start_x][start_y] = True            #방문한 곳은 

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            #범위 내에서 바다가 아닌 곳 찾기, 방문하지 않은 곳 찾기
            if 0 <= nx < n and 0 <= ny < m and board[nx][ny] != 0 and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))


n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
answer = 1

while True:
    visited = [[False] * m for _ in range(n)]
    piece = 0

    # 빙산이 다 녹을 때까지 분리되지 않은 경우
    flag = True
    for i in range(n):
        for j in range(m):
            if board[i][j] != 0:
                flag = False

    if flag:
        print(0)
        break

    # 빙산이 녹은 이후로 업데이트
    temp_board = deepcopy(board)        
    for i in range(1, n - 1):
        for j in range(1, m - 1):
            #바다가 아닌 경우
            if temp_board[i][j] != 0:
                #주변의 바다의 개수세서 빙산의 높이에서 바다의 개수를 빼준다.
                #각 칸에 저장된 높이는 0보다 더 줄어들지 않으므로, 0과 바다의 방향 개수에서 현재 빙하 높이 빼줌
                board[i][j] = max(0, board[i][j] - count_ocean(i, j))

    # 빙산 덩어리 개수 세기
    for i in range(1, n - 1):
        for j in range(1, m - 1):
            #방문하지 않은 경우, 바다가 아닌 경우 BFS 수행
            #BSF 함수가 호출된 숫자에 따라서 빙산이 분리되는 최초의 시간
            if not visited[i][j] and board[i][j] != 0:
                count_iceberg(i, j)
                piece += 1

    #두 덩어리 이상으로 분리되는 최초의 시간(년) 출력
    if piece >= 2:
        print(answer)
        break

    answer += 1

#20220717_백준_9466_텀프로젝트.py
#https://www.acmicpc.net/problem/9466