구현, BFS - 2573번: 빙산

• 빙산 녹이기: 매 해마다 ices 좌표 기준으로 사방의 바다 개수를 세고, 한꺼번에 높이를 줄여 동시 갱신하기
• 분리 여부 확인: bfs()로 빙산 덩어리 크기와 전체 빙산 개수를 비교해, 다 닿지 못하면 분리된 것으로 판정하기
• 시작 시 이미 분리된 경우 0 출력, 아니면 매 해 녹이고 분리되면 year_cnt 출력, 전부 녹으면 0 출력

from collections import deque
import sys

input = sys.stdin.readline

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

for i in range(n):
    line = list(map(int, input().split()))
    maps.append(line)
    for j in range(len(line)):
        if line[j] != 0:
            ices.append((i, j, line[j]))


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


def melt_ice():

    # 이번 턴의 melt 후보리스트
    melt_list = []
    # 이번 턴에 녹고 남은 빙산 리스트
    new_ices = []

    # 현재 빙산 리스트 전체 순회
    for i in range(len(ices)):
        x, y, h = ices[i]

        water_cnt = 0

        # 빙산 위치의 상하좌우 체크하면서 물 갯수 카운트
        for j in range(4):
            nx, ny = x + dx[j], y + dy[j]

            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 0:
                water_cnt += 1

        # 새로운 높이 계산
        new_h = h - water_cnt

        # 녹아서 물이 됐으면 melt 후보리스트에 추가 (바로 0으로 만들어버리면 안됨! 다른 빙산에 영향을 주므로 주의)
        if new_h <= 0:
            melt_list.append((x, y, h))

        # 아직 물이 되지는 않았다면 바로 갱신하기
        else:
            maps[x][y] = new_h
            new_ices.append((x, y, new_h))
            # ices[i] = (x, y, new_h)

    # 빙산을 모두 확인한 후 녹이기
    for x, y, h in melt_list:
        maps[x][y] = 0
        # ices.remove((x, y, h))

    return new_ices


def bfs():

    q = deque()
    visited = [[False] * m for _ in range(n)]

    group_cnt = 1  # 시작하는 빙산 하나 카운트

    if len(ices) > 0:
        start_x, start_y = ices[0][0], ices[0][1]
        q.append((start_x, start_y))

    # 시작 좌표 방문처리
    visited[start_x][start_y] = True

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

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

            if (
                0 <= nx < n
                and 0 <= ny < m
                and maps[nx][ny] != 0
                and not visited[nx][ny]
            ):
                group_cnt += 1
                visited[nx][ny] = True
                q.append((nx, ny))

    # 그룹이 2개 이상인 경우
    if group_cnt < len(ices):
        return False
    # 그룹이 1개인 경우
    return True


year_cnt = 0

while True:

    # 빙산이 1개 이상인 경우
    if len(ices) > 0:
        # 빙산 그룹이 2개 이상인 경우
        if not bfs():
            print(year_cnt)
            break
    # 빙산이 더 이상 없다면
    else:
        print("0")
        break

    # 빙산 녹이기
    ices = melt_ice()

    year_cnt += 1

# 1) 빙산 녹이기 : ices 리스트 돌면서 각 좌표의 maps값 갱신 및 ices 리스트 갱신

# 2) ices 리스트 중 한 좌표에서 시작해서 BFS 해서 한 번에 모든 빙산에 도달할 수 없다면 두 덩어리 이상임