[Baekjoon-Python] 17142 : 연구소 3

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

접근

바이러스 중 m개의 활성 바이러스를 조합으로 선택한다.
bfs 탐색하면서 바이러스를 퍼뜨린다.
빈 칸의 개수가 0이면 최소 시간을 갱신한다.

풀이

from sys import stdin
from collections import deque
from itertools import combinations


def bfs(virus, empty_cnt) -> int:
    q = deque(virus)
    visited = [[0] * n for _ in range(n)]
    for r, c in virus: # (1)
        visited[r][c] = 1

    while q:
        r, c = q.popleft()

        for i in range(4):
            nr, nc = r + direction[i], c + direction[3 - i]
            if is_out_of_range(nr, nc):
                continue

            if not visited[nr][nc]: # (2)
                if lab[nr][nc] == 0: # (3)
                    empty_cnt -= 1
                visited[nr][nc] = visited[r][c] + 1
                q.append((nr, nc))

            if empty_cnt == 0: # (4)
                return visited[r][c]

    return n**2 # (5)


def is_out_of_range(r, c):
    return 0 > r or r >= n or 0 > c or c >= n or lab[r][c] == 1


n, m = map(int, stdin.readline().split())
lab = []
virus = []
empty_cnt = 0
for i in range(n):
    line = list(map(int, stdin.readline().split()))
    lab.append(line)
    for j in range(n):
        if line[j] == 0:
            empty_cnt += 1
        elif line[j] == 2:
            virus.append((i, j))
if empty_cnt == 0: # (6)
    print(0)
    exit()

direction = [1, 0, -1, 0]
min_sec = n**2
for comb in combinations(virus, m): # (7)
    min_sec = min(min_sec, bfs(comb, empty_cnt))

print(min_sec if min_sec != n**2 else -1)