연구소

p.341

 

DFS

import sys
from itertools import combinations

input=sys.stdin.readline
n,m=map(int, input().split())
graph=[]
temp=[[0]*m for _ in range(n)] 
fence=[]
virus=[]
result=0

for i in range(n):
  graph.append(list(map(int, input().split())))

for i in range(n):
  for j in range(m):
    if graph[i][j]==0: # 울타리 칠 수 있는 위치
      fence.append((i,j))
    elif graph[i][j]==2: #바이러스 위치
      virus.append((i,j))

fence_c=list(combinations(fence,3)) # 울타리를 놓을 수 있는 경우의 수

da=[-1,1,0,0]
db=[0,0,-1,1]

####### dfs 함수 ########
def dfs(v_a,v_b):
  temp[v_a][v_b]=2

  for i in range(4):
    n_a=v_a+da[i]
    n_b=v_b+db[i]
    if n_a<0 or n_b<0 or n_a>=n or n_b>=m:
      continue
    elif temp[n_a][n_b]==1:
      continue
    elif temp[n_a][n_b]==0:
      dfs(n_a,n_b)
#########################


for f in fence_c:

  for i in range(n): # 울타리 위치를 바꿀 때마다 초기화
    for j in range(m):
      temp[i][j]=graph[i][j]

  for f_a,f_b in f: # 울타리 3개씩 놓아보기
    temp[f_a][f_b]=1
  
  # 바이러스인 곳 부터 dfs로 바이러스 퍼트리기
  for v in virus:
    v_a, v_b=v
    dfs(v_a,v_b)

  count=0
  # 바이러스 퍼트리고 남은 0 갯수 비교
  for i in range(n):
    for j in range(m):
      if temp[i][j]==0:
        count+=1
  
  result=max(result, count)

print(result)

 

시간이 오래걸려서 조마조마 했는데.. 맞았다 ㅠㅠㅠ