시간초과

# 0: 빈칸, 1: 벽, 2: 바이러스
# M * N 연구소 크기
from collections import deque

N,M = map(int, input().split())

grid = []
for i in range(N):
  row = list(map(int, input().split()))
  grid.append(row)

# print(grid)
# 벽을 3개 세웠을 때, 안전영역의 최대 크기 구하기

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

# 바이러스 퍼지는 함수 작성
def virusBlow():
  test_grid = [row[:] for row in grid]
  queue = deque()

  for y in range(N):
    for x in range(M):
      if test_grid[y][x] == 2:
        queue.append((x, y))

  while queue:
    cx, cy = queue.popleft()
    for i in range(4):
      nx, ny = cx + dx[i], cy + dy[i]

      if 0 <= nx < M and 0 <= ny < N:
        if test_grid[ny][nx] == 0: # 빈칸이면 바이러스 전파
          test_grid[ny][nx] = 2
          queue.append((nx, ny))

  cnt = 0
  for row in test_grid:
      cnt += row.count(0)
  return cnt

# 임의의 0 3개를 1로 전환 -> 바이러스 퍼지는 함수 실행 -> 안전영역 세기
# 안전영역이 최대가 나올 때까지 탐색

def makeWall(count):
  global max_result

  if count == 3:
    max_result = max(max_result, virusBlow())
    return
  
  for y in range(N):
    for x in range(M):
      if grid[y][x] == 0:
        grid[y][x] = 1
        makeWall(count + 1)
        # 초기화하면서 모든 경우의 수에 대해서 cnt기록
        grid[y][x] = 0

makeWall(0)
print(max_result)

해결코드

itertools.combinations

from itertools import combinations
from collections import deque

# 1. 모든 빈칸(0)의 좌표를 미리 리스트에 저장
empty_spaces = []
for y in range(N):
    for x in range(M):
        if grid[y][x] == 0:
            empty_spaces.append((x, y))

# 2. combinations를 이용해 빈칸 중 3개를 뽑는 루프
for walls in combinations(empty_spaces, 3):
    # 벽 세우기
    for wx, wy in walls:
        grid[wy][wx] = 1
    
    # 바이러스 퍼뜨리기 & 안전 영역 계산
    max_result = max(max_result, virusBlow())
    
    # 벽 다시 허물기
    for wx, wy in walls:
        grid[wy][wx] = 0

• 불필요한 루프 제거
  • 벽을 세울 수 없는 곳(1이나 2가 있는 곳)을 매번 검사하지 않고, 오직 empty_spaces만 대상
• 함수 호출 오버헤드 감소
  • 재귀 함수(makeWall)를 수만 번 호출하는 비용을 줄일 수 있음