백준 17141 파이썬

 

import sys 
from collections import deque 
from itertools import combinations

input = sys.stdin.readline

N, M = map(int, input().split())

matrix = [[] for _ in range(N)]
visited = [[] for _ in range(N)]

for i in range(N):
    row = list(map(int, input().split()))
    matrix[i] = row
    visited[i] = [False for _ in range(N)]

possible = []

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

for i in range(N):
    for j in range(N):
        if matrix[i][j] == 2:
            possible.append([i, j])


time = float('inf')
for comb in combinations(possible, M):
    comb = list(comb)
    queue = deque()

    for i in range(N):
        visited[i] = [False for _ in range(N)]

    for item in comb:
        queue.append(item) 
        r, c = item
        visited[r][c] = True 

    tempTime = 0
    while queue:
        tempTime += 1
        temp = []
        while queue: # 한 턴에 있는 요소들을 다 끄집어낸다 
            node = queue.popleft() 
            nr, nc = node

            for i in range(4):
                tr = nr + dx[i]
                tc = nc + dy[i]
                if tr >= 0 and tr < N and tc >= 0 and tc < N:
                    if not visited[tr][tc] and matrix[tr][tc] != 1:
                        visited[tr][tc] = True
                        temp.append([tr,tc])

        for item in temp:
            queue.append(item)


    isPossible = True
    for i in range(N):
        for j in range(N):
            if matrix[i][j] == 0 or matrix[i][j] == 2:
                if visited[i][j] == False:
                    isPossible = False
    

    if isPossible:
        time = min(time, tempTime)

if time == float('inf'):
    print(-1)
else: print(time-1)