from collections import deque
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
viruslist = []
answer = []
ans = -1
for i in range(n):
for j in range(m):
if g[i][j] == 2:
g[i][j] = 0
viruslist.append((i, j))
def bfs():
check = [[-1] * m for _ in range(n)]
q = deque()
for i in range(n):
for j in range(m):
if g[i][j] == 3:
q.append((i, j))
check[i][j] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx <0 or ny < 0 or nx >= n or ny >= m:
continue
if check[nx][ny] == -1 and g[nx][ny] == 0:
check[nx][ny] = check[x][y] + 1
q.append((nx, ny))
for i in range(n):
for j in range(m):
if g[i][j] != 1:
if check[i][j] == -1:
return
if tmp < check[i][j]:
tmp = check[i][j]
global ans
if ans == -1 or ans > tmp:
ans = tmp
def go(index, cnt):
if index == len(viruslist):
if cnt == m:
bfs()
else:
x, y = viruslist[index]
g[x][y] = 3
go(index+1, cnt+1)
g[x][y] = 0
go(index+1, cnt)
go(0, 0)
print(ans)from collections import deque
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
viruslist = []
ans = -1
for i in range(n):
for j in range(n):
if g[i][j] == 2:
g[i][j] = 0
viruslist.append((i, j))
def bfs():
check = [[-1] * n for _ in range(n)]
q = deque()
for i in range(n):
for j in range(n):
if g[i][j] == 3:
q.append((i, j))
check[i][j] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx <0 or ny < 0 or nx >= n or ny >= n:
continue
if check[nx][ny] == -1 and g[nx][ny] != 1:
check[nx][ny] = check[x][y] + 1
q.append((nx, ny))
tmp = 0
for i in range(n):
for j in range(n):
if g[i][j] != 1:
if check[i][j] == -1:
return
if tmp < check[i][j]:
tmp = check[i][j]
global ans
if ans == -1 or ans > tmp:
ans = tmp
def go(index, cnt):
if index == len(viruslist):
if cnt == m:
bfs()
else:
x, y = viruslist[index]
g[x][y] = 3
go(index+1, cnt+1)
g[x][y] = 0
go(index+1, cnt)
go(0, 0)
print(ans)bfs + 재귀(바이러스 놓기)
^^~