[알고리즘]백준 17141 연구소2

처음에 dfs를 통해 바이러스가 들어갈 자리를 구하다가 시간초과가 나서 파이썬 라이브러리 combination을 통해서 풀어주었다. 해결과정에서 선택되지 않은 바이러스를 놓을 수 있는자리를 어떻게 처리할까 싶어서 바이러스가 놓인 자리를 3으로 만들어주고 그 외에 바이러스가 놓일 수 있는 자리들을 같이 바꿔주었다.

import sys
from collections import deque
from itertools import combinations


n,m = map(int, input().split())

lst = [list(map(int, input().split())) for _ in range(n)]

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

visited = [[False] * n for _ in range(n)]
t = []
for i in range(n):
    for j in range(n):
        if lst[i][j] ==2:
            t.append((i,j,3))

if(not t) :
    print(0)
    exit()
answer = int(1e9)
def bfs(array, visited, row):
    global answer
    q = deque(array)
    while q:
        x, y, count = q.popleft()
        visited[x][y] == True
        if count >= answer:
            return int(1e9)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >=n or ny >= n or visited[nx][ny] == True:
                continue
            if row[nx][ny] == 0 or row[nx][ny] == 2  :
                visited[nx][ny] = True
                row[nx][ny] = count+1
                q.append((nx,ny,count+1))
    for ddd in row:
        if 0 in ddd or 2 in ddd:
            count = int(1e9)
    return count

combination = list(combinations(t, m))

for i in combination:
    v = [[False] * n for _ in range(n)]
    br = [row[:] for row in lst]
    for (x,y,z) in i:
        br[x][y] = 3

    answer = min(answer, bfs(i, v, br))

if answer != int(1e9):
    print(answer-3)
else:
    print(-1)