[백준] 14502번 연구소 _ python

전체 탐색과 bfs를 활용하겠다는 아이디어는 떠올랐으나 벽을 3개 설치하는 부분을 어떻게 구현해야 할지 감이 안와서 그냥 아이디어 찾아보고 풀었음.
더 유용한 방법이 있을거라 생각했는데 그냥 이중 for문으로 모든 경우 수행해 보는 게 답인듯.
1. 벽 3개를 설치하는 모든 경우의 수 돌림
2. 벽 3개 설치되면 설치될 때마다 bfs 수행

유의할 점
벽을 세울 때마다 center[] 달라짐.
deepcopy 사용해야 함. 그냥 매개변수로 전달해서 사용하면 안됨.

import sys
from collections import deque
import copy

n, m = map(int, sys.stdin.readline().split())
center = []
for i in range(n):
    temp = list(map(int, list(sys.stdin.readline().split())))
    center.append(temp)

max_safe = 0
virus_loc = []
for a in range(n):
    for b in range(m):
        if center[a][b] == 2:
            virus_loc.append((a,b))

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

def bfs(now_center):
    global max_safe
    queue = deque()
    queue.extend(virus_loc)
    while queue:
        virus = queue.popleft()
        for d in range(4):
            vx = virus[0] + dx[d]
            vy = virus[1] + dy[d]
            if vx < 0 or vy < 0 or vx >= n or vy >= m:
                continue
            elif now_center[vx][vy] == 0:
                now_center[vx][vy] = 2
                queue.append((vx,vy))

    safe_count = 0
    for c in range(n):
        safe_count += now_center[c].count(0)
    max_safe = max(max_safe, safe_count)

def make_wall(cnt):
    if cnt == 3:
        bfs(copy.deepcopy(center))
        return

    for e in range(n):
        for f in range(m):
            if center[e][f] == 0:
                center[e][f] = 1
                make_wall(cnt+1)
                center[e][f] = 0

make_wall(0)
print(max_safe)