백준 구현 대비 연구소

문제:https://www.acmicpc.net/problem/14502

문제 도식화

1.벽 3개 선택 (combinations 활용, 최대 64 C 3)
2.bfs ( 최대 8x8 )
3.그래프 내 0인 공간의 갯수 계산 ( 완탐이므로 최대 8x8 )

수행 과정은 1x(2+3)
시간복잡도는 대충 64^3*128==30000000
구현 ㄱㄱ

전체코드

from itertools import combinations
import copy
from collections import deque
total=0

def bfs(graph,N,M):
  global total
  answer=0
  move=[[1,0],[0,1],[-1,0],[0,-1]]
  queue=deque()
  for i in range(N):
    for j in range(M):
      if graph[i][j]==2:
        queue.append([i,j])
  visited=[[0 for i in range(M)] for j in range(N)]

  for qu in queue:
    visited[qu[0]][qu[1]]=1
  while queue:
    cur=queue.popleft()
    ci,cj=cur[0],cur[1]
    for mo in move:
      ni,nj=ci+mo[0],cj+mo[1]
      if 0<=ni<N and 0<=nj<M and graph[ni][nj]==0 and visited[ni][nj]==0:
        queue.append([ni,nj])
        visited[ni][nj]=1
        graph[ni][nj]=2
  
  for i in range(N):
    for j in range(M):
      if graph[i][j]==0:
        answer+=1
  total=max(total,answer)
#0은 빈칸
#1은 벽
#2는 바이러스
walllist=[]
N,M=map(int, input().split())
graph=[]
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:
      walllist.append([i,j])

walllist=list(combinations(walllist,3))

# 벽 3개

for wall in walllist:
  tempgraph=copy.deepcopy(graph)
  for cw in wall:
    tempgraph[cw[0]][cw[1]]=1
  bfs(tempgraph,N,M)

print(total)