코드

# 연구소
"""
1. 벽 3개 세우기
2. 바이러스 확산
3. 안전영역 최댓값 갱신
BFS / DFS 활용해야 할 것 같음
"""
import copy
import sys
from collections import deque

def bfs():
    global result
    map_copy = copy.deepcopy(tmp)
    for i in range(n):
        for j in range(m):
            if map_copy[i][j] == 2:
                dq.append([i,j])
    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 map_copy[nx][ny] == 0: # 값이 0이라면 바이러스 전염됨
                    map_copy[nx][ny] = 2
                    dq.append([nx,ny])
    cnt = 0
    for data in map_copy:
        cnt += data.count(0) # 안전영역(0인 값) 체크
    result = max(result,cnt) # 값 비교 후 최댓값으로 업데이트

def wall(x):
    if x == 3:
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 0:
                tmp[i][j] = 1
                wall(x+1)
                tmp[i][j] = 0

# 방향 값
dx = [0, 0, 1, -1]
dy = [1, -1, 0 , 0]

n,m = map(int,sys.stdin.readline().split())
tmp = []
dq = deque()
# 지도 만들기
for _ in range(n):
    tmp.append(list(map(int, sys.stdin.readline().split())))

result = 0
wall(0)
print(result)

bfs는 구현했는데 벽 세우는 부분을 잘 모르겠어서 구글링 했습니다.