백준
1. DFS
import sys
import copy
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
result = -sys.maxsize
virus = []
for i in range(n):
for j in range(m):
if board[i][j] == 2:
virus.append((i, j))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def check(keep):
now = 0
for i in range(n):
for j in range(m):
if keep[i][j] == 0:
now += 1
return now
def go(x, y, keep):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and keep[nx][ny] == 0:
keep[nx][ny] = 2
go(nx, ny, keep)
def dfs(count):
global result
if count == 3:
keep = copy.deepcopy(board)
for x, y in virus:
go(x, y, keep)
result = max(result, check(keep))
return
for i in range(n):
for j in range(m):
if board[i][j] == 0:
board[i][j] = 1
dfs(count + 1)
board[i][j] = 0
dfs(0)
print(result)
`