[ BOJ / 파이썬 ] 2573 빙산

/  제출 1  /  : 35분 소요

import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
board = [list(map(int, input().split())) for _ in range(n)]

cnt = 0

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

        result += 1
  return result         
               
  
while True:
  q = deque([])
  cnt += 1

  for x in range(n):
    for y in range(m):
      if board[x][y] != 0:
        zero = 0
        for i in range(4):
          nx = x + dx[i]
          ny = y + dy[i]
          if board[nx][ny] == 0:
            zero += 1
        if zero != 0:
          q.append((x, y, zero))

  if not q:
    print(0)
    break
  else:
    while q:
      x, y, meltCnt = q.popleft()
      board[x][y] =  board[x][y] - meltCnt if board[x][y] - meltCnt  > 0 else 0

  iceberg = getIceBergNum()
  if iceberg >= 2:
    print(cnt)
    break

 

: 34 % 까지가다가 시간 초과 

: 나름 논리적으로 짰다고 생각했는데, 중복 되는 부분이 있나보다.. 시간복잡도 계산해보고 개선해보겠다.

 

 

아니 뭐 이런...

Python으로 제출했을 때 시간 초과로 끝나서 이리 개선, 저리 개선했는데 더 꼬이는 것 같아 다른 풀이를 봤다.

Python으로 제출하면 시간 초과나셨다고 PyPy3로 제출했다고 해서 나도 혹시나 하고 해봤는데, 맞았습니다가 떴다.

 

내 40분 돌리도... 하하