[백준 14502] 연구소

import sys

import time

Tstart = time.time()

def xy(node):
    x=node//n
    y=node%n
    return x,y

def BFS(M, start_node):
    visited = list()
    queue = list()

    queue.append(start_node)

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            x=node//n
            y=node%n
            if y!=n-1 and M[node+1]==0: 
                M[node+1]=2
                queue.append(node+1)
            if y!=0 and M[node-1]==0: 
                M[node-1]=2
                queue.append(node-1)
            if x!=m-1 and M[node+n]==0:
                M[node+n]=2
                queue.append(node+n)            
            if x!=0 and M[node-n]==0: 
                M[node-n]=2
                queue.append(node-n) 
     
    return visited

m,n=map(int, sys.stdin.readline().split())

OM=[]
Virus_list_Original=[]
Zero_list=[]
 
for i in range(m):
    OM+=list(map(int, sys.stdin.readline().split()))
    for j in range(n):
        if OM[i*n+j]==2:
            Virus_list_Original.append(i*n+j)
        if OM[i*n+j]==0:
            Zero_list.append(i*n+j)

from itertools import combinations

Mans=0
for k in list(combinations(Zero_list,3)):
    M=OM[:]
    M[k[0]]=1
    M[k[1]]=1
    M[k[2]]=1
 
 
    Virus_list=Virus_list_Original[:]
    while Virus_list:
        sp=Virus_list.pop(0)
        BFS(M,sp)
        
    ans=0
    for i in range(m):
        for j in range(n):
            if M[i*n+j]==0 :
                ans+=1
    if Mans<ans:

        Mans=ans
    
    M[k[0]]=0
    M[k[1]]=0
    M[k[2]]=0    

print("Total Times is", time.time()-Tstart)
print(Mans)