이번 문제는 백트레킹을 통해 바이러스가 존재하는 모든 경우를 구하고, 각 경우마다 BFS를 통해 바이러스가 퍼지는 시간을 갱신하는 방식으로 구현하였다. 각 칸의 바이러스가 퍼지는 시간이 짧은 것이 우선순위가 높으므로 항상 더 작은 값으로 갱신해주었다. 다익스트라 방식과 유사하다고 할 수 있다.

Code

from collections import deque
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
virus_possible = []
for i in range(n):
    for j in range(n):
        if grid[i][j] == 2:
            virus_possible.append((i, j))
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
viruses = []
def get_viruses(cur, virus):
    if cur == len(virus_possible):
        if len(virus) == m:
            viruses.append(virus)
        return
    if len(virus) > m:
        return
    get_viruses(cur+1, virus+[virus_possible[cur]])
    get_viruses(cur+1, virus)
def spread_viruses(virus):
    q = deque()
    visited = [[1e9 for _ in range(n)] for _ in range(n)]
    result = 0
    for y, x in virus:
        visited[y][x] = 0
        q.append((y, x, 0))
    while q:
        y, x, time = q.popleft()
        if time > visited[y][x]:
            continue
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < n and grid[ny][nx] != 1 and visited[ny][nx] > visited[y][x]+1:
                q.append((ny, nx, time+1))
                visited[ny][nx] = min(time+1, visited[ny][nx])
    for i in range(n):
        for j in range(n):
            if grid[i][j] != 1 and visited[i][j] != 1e9:
                result = max(result, visited[i][j])
            elif grid[i][j] != 1 and visited[i][j] == 1e9:
                result = 1e9
                return result
    return result
answer = 1e9
get_viruses(0, [])
for i in range(len(viruses)):
    answer = min(answer, spread_viruses(viruses[i]))
if answer == 1e9:
    answer = -1
print(answer)