14502번 백준

backTracking dfs

python3로 진행시 시간 초과 pypy3로 채점 §

from sys import stdin
import collections
N, M = map(int, stdin.readline().split(" "))
 
dx = [0,0,1,-1]
dy = [1,-1,0,0]
graph = []
zeroBlock = 0
virusStartList =[]
ans = -1
for i in range(N):
  temp = list(map(int, stdin.readline().split(" ")))
  graph.append(temp)
  for j in range(len(temp)):
    if temp[j] == 0:
      zeroBlock+=1
    elif temp[j] == 2:
      virusStartList.append([i,j])
 
 
def backTracking(wallCnt):
  global N, M, ans,graph
  
  if wallCnt == 3:
    conflit = bfs(virusStartList)
    result =zeroBlock - conflit
    if  result>ans:
      ans = result
      return
    return
  
  for n in range(N):
    for m in range(M):
      if graph[n][m] == 0 :
        graph[n][m] =1
        wallCnt = wallCnt+1
        backTracking(wallCnt)
        graph[n][m] =0
        wallCnt = wallCnt-1
        
 
def bfs(virusList):
  global N, M
  q = collections.deque()
  visit = [[False for _ in range(M)] for _ in range(N)]
  for virus in virusList:
    q.append(virus)
  cnt =0
  while q:
    now =  q.popleft()
    for i in range(4):
      nr = now[0] + dx[i]
      nc = now[1] + dy[i]
      if nr>=0 and nr<N and 0<= nc <M and not visit[nr][nc] and graph[nr][nc] == 0:
        visit[nr][nc] = True
        cnt+=1
        q.append([nr,nc])
  return cnt
 
backTracking(0)
print(ans-3)