백준 boj. 17142 연구소 3 [골드 🥇🥇🥇]

from collections import deque
import sys

N, M = map(int, sys.stdin.readline().split())
grid = []
vs = []
ans = 1e8

for _ in range(N):
  grid.append(list(map(int, sys.stdin.readline().split())))
vs = [(i, j) for i in range(N) for j in range(N) if grid[i][j] == 2]
n_empty = len([(i, j) for i in range(N) for j in range(N) if grid[i][j] == 0])

def find_mn_dist(accm_virus, v):
  global ans
  global n_empty

  dq = deque()
  for vi, vj in accm_virus:
    dq.append((vi, vj))

  while dq:
    if n_empty == 0: break

    ci, cj = dq.popleft()
    for dx, dy in ((-1,0),(1,0),(0,1),(0,-1)):
      ni, nj = ci+dx, cj+dy

      if 0 <= ni < N and 0 <= nj < N and v[ni][nj] == -1:
        if grid[ni][nj] == 0:
          v[ni][nj] = v[ci][cj] + 1
          dq.append((ni, nj))
          n_empty -= 1
        if grid[ni][nj] == 2:
          v[ni][nj] = v[ci][cj] + 1
          dq.append((ni, nj))

  if n_empty > 0:
    return
  else:
    t = max([max(each) for each in v])
    ans = min(ans, t)
    return

def dfs(m, start, v, accm_virus):
  global n_empty

  if m == M:
      n_empty = len([(i, j) for i in range(N) for j in range(N) if grid[i][j] == 0])
      find_mn_dist(accm_virus, v)  # 활성화된 바이러스 조합 출력
      return

  for i in range(start, len(vs)):  # start 인덱스를 추가하여 중복 방지
    vi, vj = vs[i]
    if v[vi][vj] == -1: 
      v[vi][vj] = 0  # 방문 처리
      accm_virus.append((vi, vj))

      new_v = [e_r[:] for e_r in v]
      dfs(m+1, i+1, new_v, accm_virus)  # 다음 DFS 호출 시 i+1로 범위 제한

      v[vi][vj] = -1  # 방문 원상복구
      accm_virus.pop()

# 1. 활성화 할 바이러스 조합 DFS로 찾기.
v = [[-1] * N for _ in range(N)]

dfs(0, 0, v, [])

if ans == 1e8:
  print(-1)
else:
  print(ans)