[백준] 17142 - 연구소 3 (파이썬)

from itertools import combinations
from collections import deque
n , m = map(int,input().split())
array = []
for _ in range(n):
    array.append(list(map(int,input().split())))
virus = []
for i in range(n):
    for j in range(n):
        if array[i][j] == 2:
            virus.append([i,j,0])
choice = deque(combinations(virus,m))
dx = [-1,0,1,0]
dy = [0,1,0,-1]

def check(visit):
    for i in range(n):
        for j in range(n):
            if visit[i][j] == False and array[i][j] == 0:
                return False
    return True
def BFS():
    k = 0
    visit = [[False for _ in range(n)] for _ in range(n)]
    
    while q:
        a = q.popleft()
        x = a[0]
        y = a[1]
        time = a[2]
        visit[x][y] = True
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if array[nx][ny] == 0 and visit[nx][ny] == False:
                    visit[nx][ny] = True
                    q.append((nx,ny,time+1))
                    k = max(k,time+1)
                elif array[nx][ny] == 2 and visit[nx][ny] == False:
                    q.append((nx,ny,time+1))
                    # 2는 남아도 괜찮아서 k값 비교하지 않음
    if check(visit):
        return k
    else:
        return 2505
total = 2505
for i in range(len(choice)):
    q = deque(choice[i])
    total = min(total,BFS())
if total == 2505:
    print(-1)
else:
    print(total)

total은 배열 최대크기가 2500이라서 넉넉하게 2505로 시작했다.

이 문제에서 비활성화 바이러스 다루는게 제일 관건이었다고 생각한다.

처음부터 모든 바이러스를 방문했다고 처리 할 경우 그쪽 방향으로 더 진행할 수 없기 때문에

k값 비교만 안하는 걸로 해결하였다.