인프런 커뮤니티 질문&답변

import queue
import copy

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

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
min = 2147000000
max = -min
cnt = 0

for i in range(n):
    for j in range(n):
        if arr[i][j] > max:
            max = arr[i][j]
        if arr[i][j] < min:
            min = arr[i][j]

start = min+1
end = max

for val in range(start,end):
    q = queue.Queue()
    region = 0
    tmp = copy.deepcopy(arr)
    for i in range(n):
        for j in range(n):
            if tmp[i][j] > val:
                q.put((i,j))
                tmp[i][j] = 0
                region += 1
                while q.qsize() > 0:
                    now = q.get()
                    for k in range(4):
                        nx = now[0]+dx[k]
                        ny = now[1]+dy[k]
                        if 0<= nx < n and 0<= ny < n and tmp[nx][ny] > val:
                            tmp[nx][ny] = 0
                            q.put((nx,ny))
    if region > cnt:
        cnt = region

print(cnt)

BFS방식으로 풀었을 때 5번에서 시간초과가 뜹니다 ㅠㅠ

위 소스처럼 tmp = copy.deepcopy(arr) 방식 말고

ch =[[0]*n for _ in range(n)] 로 체크만 하는 경우에도 똑같이 5번에서 시간 초과가 뜨네요..

혹시 개선할만한 부분이 있을까요?