[백준] 14502 연구소(파이썬)

벽의 개수가 3개보다 적으면 벽을 세우고 3일때 바이러스 전파 후 0의 개수를 센다.
마지막으로 벽을 세운곳의 벽을 없애고 다음 자리에 벽을 세우고 계산한다.
전파와 0의 개수는 bfs 함수로 벽을 세우는건 재귀를 통해서 구현했는데
pypy로는 통과하지만 python으로 제출하는 경우 시간초과로 통과하지 못함

import sys 
from collections import deque
import copy
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
virus = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(n):
  for j in range(m):
    if graph[i][j] == 2:
      virus.append((i, j))

def bfs(board):
  temp = copy.deepcopy(board)
  res = 0
  dq = deque([])
  for i in virus:
    dq.append(i)

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

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

      if 0 <= nx < n and 0 <= ny < m:
        if temp[nx][ny] == 1:
          continue
        if temp[nx][ny] == 0:
          temp[nx][ny] = 2
          dq.append((nx, ny))
  for i in range(n):
    for j in range(m):
      if temp[i][j] == 0:
        res += 1
  return res

def recursion(level):
  count = 0
  if level == 3:
    return bfs(graph)

  for i in range(n):
    for j in range(m):
      if graph[i][j] == 0:
        graph[i][j] = 1
        count = max(count, recursion(level+1))
        graph[i][j] = 0

  return count

print(recursion(0))