BOJ - 14502 - 연구소

import sys
import copy
from collections import deque

result = 0

def BFS(maps, N, M):
    global result
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    copyMap = copy.deepcopy(maps)

    virus = deque()
    for i in range(N):
        for j in range(M):
            if copyMap[i][j] == 2:
                virus.append((i, j))

    while virus:
        x, y = virus.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if copyMap[nx][ny] == 0:
                    copyMap[nx][ny] = 2
                    virus.append((nx, ny))

    tmp = 0
    for i in range(N):
        for j in range(M):
            if copyMap[i][j] == 0:
                tmp += 1

    result = max(result, tmp)

def setWall(maps, N, M, cnt):
    if cnt == 3:
        BFS(maps, N, M)
        return

    for i in range(N):
        for j in range(M):
            if maps[i][j] == 0:
                maps[i][j] = 1
                setWall(maps, N, M, cnt+1)
                maps[i][j] = 0

def solution():
    N, M = map(int, sys.stdin.readline().split())
    maps = []
    for _ in range(N):
        maps.append(list(map(int, sys.stdin.readline().split())))

    setWall(maps, N, M, 0)
    print(result)
solution()

https://www.acmicpc.net/problem/14502