✅문제 요약

1. nxn 연구소
2. 바이러스는 2, 벽은1, 0은 통로
3. 바이러스가 최소로 퍼질 수 있는 벽 3개를 설치했을 때 안전영역 크기 출력

✅문제 풀이

보자마자 이거 시간 오래걸릴 것 같은데..라는 생각이 들었고, 당연히 시간제한이 클 것으로 생각돼서 브루트포스 말고 경제적인 방법을 고안하느라 애를 먹었다.
그냥 일단 브루트포스 방법을 만들고 하나씩 경우를 지우면 빨라지는걸 꽤나 늦은 시간에 깨달았다..
일단 풀자!

풀이는 이렇다
1. 벽 다 세우기
2. 세균 위치들 탐색
3. 각 세균 위치에서 4방향 이동 함수 실행
4. 안전구역 검사

def wall(n, si):        # 벽 수, 행번호
    global safe


    if n == 3:										# 벽을 모두 세웠으면 세균을 퍼뜨린다
        visit = [[False]*M for _ in range(N)]       # visit으로도 gyuns 검사 가능
        matrix = [arr[i][::] for i in range(N)]
        gyuns = germ[::]

        while gyuns:
            nr, nc = gyuns.pop(0)
            visit[nr][nc] = True
            matrix[nr][nc] = 2

            for idx in range(4):
                gr, gc = nr + dr[idx], nc + dc[idx]
                if 0 <= gr < N and 0 <= gc < M and visit[gr][gc] == False and matrix[gr][gc] == 0:
                    gyuns.append([gr, gc])
                    visit[gr][gc] = True

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

        if cnt > safe:
            safe = cnt
        return

    for i in range(N):
        for j in range(M):
            if i >= si and arr[i][j] == 0:		# 가지치기
                arr[i][j] = 1
                wall(n+1, i)
                arr[i][j] = 0

N, M = map(int, input().split())     # 세로 가로
arr = [list(map(int, input().split())) for _ in range(N)]

germ = []

for a in range(N):
    for b in range(M):
        if arr[a][b] == 2:
            germ.append([a, b])

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

safe = 0        # 안전구역
wall(0, 0)
print(safe)