[BOJ] 17142

me

import sys
from collections import deque
from copy import deepcopy
from itertools import combinations
input = sys.stdin.readline

n,m = map(int,input().split())
spaces=[list(map(int,input().split())) for _ in range(n)]
viruses=[]
has_blank=False
for i in range(n):
    for j in range(n):
        if spaces[i][j]==2:
            viruses.append([i,j])
        elif spaces[i][j]==0: has_blank=True
if not has_blank:
    print(0)
    sys.exit()
def spread(activated,spaces):
    dx=[-1,0,+1,0]
    dy=[0,-1,0,+1]
    q=[]
    visited=[[False]*n for _ in range(n)]
    for x,y in activated:
        q.append([0,x,y])
        spaces[x][y]=-2
        visited[x][y]=True
    q = deque([[0,x,y] for x,y in activated])
    while q:
        time,x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i];
            ny = y + dy[i];
            if not (-1 < nx < n and -1 < ny < n) or visited[nx][ny]: continue
            visited[nx][ny]=True # 방문으로 바꾸기
            if spaces[nx][ny] ==0 :
                # 벽만 아니면 모두 복제
                spaces[nx][ny] = time+1 # 바이러스로 복제 (시간으로 바꿔두기)
                q.append([time+1, nx, ny])
            elif spaces[nx][ny]==2:
                spaces[nx][ny]=-3
                q.append([time+1,nx,ny])
            else:
                spaces[nx][ny]=-1
    time=0
    for space in spaces:
        if space.count(0)!=0:
            return -1
        time = max(time,max(space))
    return time

def choose():
    global min_time
    for activated in combinations(viruses,m):
        time = spread(activated,deepcopy(spaces))
        if time != -1:
            # -1이면 모든 빈칸에 퍼뜨리지 못한 상태
            min_time=min(min_time,time)

min_time=int(1e9)
choose()
if min_time==int(1e9):
    print(-1)
else:
    print(min_time)

others

def bfs(virus_list):
    dist = [[-1] * N for _ in range(N)]
    dq=deque()
    for pos in virus_list:
        dq.append(pos)
        dist[pos[0]][pos[1]] = 0
    max_dist=0
    while dq:
        x,y=dq.popleft()
        for k in range(4):
            nx=x+di[k][0]
            ny=y+di[k][1]

            if 0<=nx<N and 0<=ny<N and map_data[nx][ny]!=1 and dist[nx][ny]==-1:
                dist[nx][ny]=dist[x][y]+1
                if map_data[nx][ny]==0:
                    max_dist=max(max_dist,dist[nx][ny])
                dq.append([nx,ny])

    a = list(sum(dist,[]))
    if a.count(-1)==list(sum(map_data,[])).count(1):	# 방문 안 한 곳이 벽의 개수와 동일한지
        ans.append(max_dist)	# 리스트없이 바로 min값 구해도 됨