Baekjoon 에 있는 BFS / DFS 문제이다. deque 라이브러리를 사용했고 추가로 3개의 벽을 세우는 과정에서 조합(combination) 라이브러리를 사용하였다.
먼저 벽 3개를 세운 후 바이러스를 큐에 넣는 방식으로 BFS를 진행하였다. 벽 3개를 효과적으로 세우는 방법을 생각해봤지만 별 방법이 없는 것 같았고
from itertools import combinations 로 조합을 사용하여 모든 경우의 수를 테스트했다.
from sys import stdin
from collections import deque
from itertools import combinations
n, m = map(int, stdin.readline().split())
origin = [list(map(int, stdin.readline().split())) for _ in range(n)]
# 조합으로 벽 3개 세우고 -> 바이러스 기준으로 BFS -> 0의 개수 max인 경우 구하기
space, virus = [], deque()
answer = 0
for i in range(n):
for j in range(m):
if origin[i][j] == 0:
space.append((i, j))
elif origin[i][j] == 2:
virus.append((i, j))
# 모든 조합의 경우 고려하기
for wall in combinations(space, 3): #( (1,2), (3,4), (1,3) )
case = [origin[i][:] for i in range(n)]
for i in range(3):
case[wall[i][0]][wall[i][1]] = 1
# BFS
queue = deque(virus)
while queue:
x, y = queue.popleft()
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
if 0 <= x + dx < n and 0 <= y + dy < m:
if case[x + dx][y + dy] == 0:
queue.append((x+dx, y+dy))
case[x+dx][y+dy] = 2
# space 개수 세기
res = 0
for c in case:
res += c.count(0)
answer = max(answer, res)
print(answer)여러 경우의 수를 고려해야하기 때문에 origin 이라는 원본 배열을 두고 이 2차원 배열을 반복문을 돌 때마다 복사해 주어야 한다. 여기서 from copy import deepcopy를 쓸 수 있지만
이는 시간이 오래 걸린다 해서 아래와 같이 2차원 배열을 복사했다.
case = [origin[i][:] for i in range(n)]