[BOJ] 14502번 연구소 python

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

문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

input 1
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

output 1
27

input 2
4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

output 2
9

import sys
import copy

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    global answer
    q = copy.deepcopy(virus)
    tmp = [[0] * m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            tmp[i][j] = arr[i][j]

    while len(q) != 0:
        t = q.pop()
        x = t[0]
        y = t[1]

        for t in range(4):
            nx = x + dx[t]
            ny = y + dy[t]
            if -1 < nx < n and -1 < ny < m:
                if tmp[nx][ny] == 0:
                    tmp[nx][ny] = 2
                    q.append([nx, ny])

    cnt = 0
    for i in tmp:
        for j in i:
            if j == 0:
                cnt += 1
    answer = max(cnt, answer)


def wall(x):
    if x == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if arr[i][j] == 0:
                arr[i][j] = 1
                wall(x + 1)
                arr[i][j] = 0


n, m = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
answer = 0
virus = []

for i in range(n):
    for j in range(m):
        if arr[i][j] == 2:
            virus.append([i, j])

wall(0)
print(answer)

BFS와 Brute Force를 사용하여 풀었다. 벽을 어떻게 세워야 하나 고민하다가 결국 구글링을 했고, 내가 본 풀이들은 가능한 모든 경우에 대하여 벽을 세워서 안전 영역에 가장 큰 경우 찾는 것들이었다. 나도 딱히 다른 방법을 떠올리지 못하여서 똑같이 풀었는데 역시나 느려 파이썬으로는 통과하지 못했다. pypy로는 통과할 수 있었지만 메모리 측면에서 효율이 굉장히 떨어지는 풀이인듯하다. 다른 방법을 찾아보는 것이 좋을 것 같다.