[Python 3] 백준 14502-연구소

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

14502번: 연구소

벽을 세우는 경우의 수는 4만 가지를 넘지 않는다. 따라서 모든 경우에 대해 다 계산해 봐도 OK.

따라서, 벽 3개를 세운 이후, 바이러스의 위치에서 BFS를 통해 이동할 수 있는 모든 빈 공간을 탐색하고, 탐색이 불가능한 공간의 개수의 최대값을 return하면 된다.

copy 라이브러리의 deepcopy를 이용하면 원본에 영향을 주지 않고 복사본을 수정 가능.

import sys
import itertools
import copy
from collections import deque

dx=[1, -1, 0, 0]
dy=[0, 0, 1, -1]
N, M=map(int, sys.stdin.readline().split())
graph=[]
virus=[]
space=[]
for i in range(N):
  x=list(map(int, sys.stdin.readline().split()))
  for j in range(M):
    if x[j]==2:
      virus.append((j, i))
    if x[j]==0:
      space.append((j, i))
  graph.append(x)

def bfs(g, x, y):
  q=deque()
  q.append((x, y))
  while q:
    now=q.popleft()
    nx=now[0]
    ny=now[1]
    for i in range(4):
      x2=nx+dx[i]
      y2=ny+dy[i]
      if x2<0 or y2<0 or x2>=M or y2>=N:
        continue
      if g[y2][x2]==0:
        q.append((x2, y2))
        g[y2][x2]=2
walls=list(itertools.combinations(space, 3))
ret=0
for wall in walls:
  temp=copy.deepcopy(graph)
  for j in wall:
    temp[j[1]][j[0]]=1
  for i in virus:
    bfs(temp, i[0], i[1])
  temp2=0
  for i in temp:
    for j in i:
      if j==0:
        temp2+=1
  if ret<temp2:
    ret=temp2
print(ret)