https://www.acmicpc.net/problem/17142

1. 코드

from itertools import combinations
from collections import deque

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

ans = 99999
N, M = map(int, input().split())
og_graph = [list(map(int, input().split())) for _ in range(N)]
lst = []
for i in range(N):
    for j in range(N):
        if og_graph[i][j] == 2:
            lst.append((i, j))

for case in list(combinations(lst, M)):
    q = deque()
    active = set()  # 활성화 바이러스 좌표
    un_active = set()  # 비활성화 바이러스 좌표
    for virus in lst:
        if virus in case:
            active.add(virus)
            q.append(virus)
        else:
            un_active.add(virus)

    graph = [[0] * N for _ in range(N)]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if og_graph[nx][ny] != 1:  # 벽이 아니고
                    if og_graph[nx][ny] != 1 and graph[nx][ny] == 0 and (nx, ny) not in active:
                        graph[nx][ny] = graph[x][y] + 1
                        q.append((nx, ny))

    for x, y in case:
        graph[x][y] = 0

    max_value = -1
    zero_cnt = 0
    for i in range(N):
        for j in range(N):
            if og_graph[i][j] != 1:
                if (i, j) in un_active:
                    continue
                if graph[i][j] == 0:
                    zero_cnt += 1
                max_value = max(max_value, graph[i][j])
    if zero_cnt == M:
        ans = min(ans, max_value)

if ans == 99999:
    print(-1)
else:
    print(ans)