[백준] 연구소

접근 방법 : 브루트포스, BFS, combinations, deepcopy

벽을 세우는 조건에서 시도도 못했다.
조건을 확인하여 브루트포스가 가능한 지 확인.
실제 시험에서는 그냥 try 해야지.

# -*- coding: utf-8 -*-
import sys
from itertools import combinations
from copy import deepcopy
from collections import deque

N, M = map(int, sys.stdin.readline().strip().split())
# board = [list((map(int, sys.stdin.readline().strip().split()))) for _ in range(N)]
board = []

virus_list = []
zero_list = []
area_max = 0

for i in range(N):
    input_list = list((map(int, sys.stdin.readline().strip().split())))
    for j in range(M):
        if input_list[j] == 0:
            zero_list.append([i, j])
        elif input_list[j] == 2:
            virus_list.append([i, j])
    board.append(input_list)

com_list = list(combinations(zero_list, 3))

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

def bfs(v_list, t_board):
    area_count = 0

    while v_list:
        x_virus, y_virus = v_list.popleft()

        for i in range(4):
            nx = x_virus + dx[i]
            ny = y_virus + dy[i]

            if 0 <= nx < N and 0 <= ny < M:
                if t_board[nx][ny] == 0:
                    t_board[nx][ny] = 2
                    v_list.append([nx, ny])
                    
    
    for chk in t_board:
        area_count += chk.count(0)
    
    return area_count



for case in com_list:
    temp_board = deepcopy(board)
    temp_deque = deque(virus_list)
    for elem in case:
        temp_board[elem[0]][elem[1]] = 1
    
    area_max = max(area_max, bfs(temp_deque, temp_board))


print(area_max)