[ BOJ / 파이썬 ] 2573. 빙산

 

오예 : ) 간만에 한 번에 뚫었다. 

 

from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def get_iceberg_num(board):
  n, m = len(board), len(board[0])
  count = 0
  visited = [[False] * m for _ in range(n)]
  
  for i in range(n):
    for j in range(m):
      if board[i][j] != 0 and not visited[i][j]:
        count += 1
        q = deque([(i, j)])
        visited[i][j] = True
        while q:
          x, y = q.popleft()
          for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            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))
  return count


  
def melt(board):
  n, m = len(board), len(board[0])
  iceberg = []
  for x in range(n):
    for y in range(m):
      if board[x][y] != 0:
        face_sea_count = 0
        for k in range(4):
          nx = x + dx[k]
          ny = y + dy[k]
          if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 0:
            face_sea_count += 1
        iceberg.append((x, y, face_sea_count))
  for ice in iceberg:
    i, j, num = ice
    melted = board[i][j] - num
    if melted >= 0:
      board[i][j] = melted
    else:
      board[i][j] = 0
  return board
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
iceberg = get_iceberg_num(board)
year = 0
while 0 < iceberg < 2:
  board = melt(board)
  iceberg = get_iceberg_num(board)
  year += 1

if iceberg == 0:
  print(0)
else:
  print(year)