[백준] 연구소.py

import sys
from copy import deepcopy
from itertools import combinations
from collections import deque
n, m = map(int, sys.stdin.readline().split())
maps, empty_wall, virus = [], [], []
dirs = [(0,1),(1,0),(-1,0),(0,-1)]

for y in range(n):
    tmp = list(map(int, sys.stdin.readline().split()))
    for x in range(m):
        # 기둥의 좌표 저장
        if tmp[x] == 0:
            empty_wall.append((y, x))
        elif tmp[x] == 2:
        # 바이러스의 좌표 저장
            virus.append((y, x))
    # 원본 maps 저장
    maps.append(tmp)

def count_zero(maps):
    count = 0
    for y in range(len(maps)):
        for x in range(len(maps[0])):
            if maps[y][x] == 0:
                count += 1
    return count

def bfs(start, candidate, maps):
    # 원본 map을 보존한 채 BFS 순회를 해야 함
    maps = deepcopy(maps)
    
    # 기둥을 세우기로 선택한 좌표를 반영한다
    for y, x in candidate:
        maps[y][x] = 1
    queue = deque()
    queue.extend(start)
    while queue:
        y, x = queue.popleft()
        for dy, dx in dirs:
            ny, nx = y+dy, x+dx
            if 0 <= ny < len(maps) and 0 <= nx < len(maps[0]) and maps[ny][nx] == 0:
                maps[ny][nx] = 2
                queue.append((ny, nx))
    return count_zero(maps)
    
# 빈 곳에 기둥을 세우기 위한 경우의 수    
candidates = list(combinations(empty_wall, 3))

max_value = 0
for i in candidates:
    result = bfs(virus, list(i), maps)
    if max_value < result:
        max_value = result
        
print(max_value)