문제

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

나의 코드

"""

"""

from sys import maxsize
from copy import deepcopy
from collections import deque
from sys import stdin
from itertools import combinations
input = stdin.readline

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


virus = [] # 처음 비활성 바이러스 들의 좌표
for i in range(n): # 최소 시간을 세야하기 때문에 기존에 입력된 값들을 다른 값으로 변경 시켜준다.
    for j in range(n):
        if pan[i][j] == 2: # 비활성 바이러스는 -1로 저장
            virus.append((i, j))
            pan[i][j] = -1
        elif pan[i][j] == 1: # 벽은 -2로 저장
            pan[i][j] = -2
        elif pan[i][j] == 0: # 빈칸은 -3로 저장
            pan[i][j] = -3

dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def bfs(com):

    copy_pan = deepcopy(pan) # 판의 값이 계속 바뀌므로 임시 변수에 계속 복사해준다.
    blank = 0 # 빈칸의 개수

    for x, y in com:
        copy_pan[x][y] = 0 # 넘겨받은 조합의 바이러스를 활성상태로 바꿈.

    for q in range(n): # 빈칸의 개수를 세어준다.
        for w in range(n):
            if copy_pan[q][w] == -3:
                blank += 1

    q = deque(com)

    while q and blank:

        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]

            if 0 <= mx < n and 0 <= my < n:
                if copy_pan[mx][my] == -3: # 빈칸을 만난 경우 바이러스를 퍼뜨린다.
                    copy_pan[mx][my] = copy_pan[px][py] + 1
                    q.append((mx, my))
                    blank -= 1
                elif copy_pan[mx][my] == -1: # 비활성 바이러스를 만난 경우 활성 바이러스로 전환한다.
                    copy_pan[mx][my] = copy_pan[px][py] + 1
                    q.append((mx, my))

    time = 0
    for i in copy_pan:
        time = max(time, max(i)) # 최소 시간을 저장한다.

        if min(i) == -3: # 빈칸이 남아있으면 maxsize를 리턴
            return maxsize
    return time

answer = maxsize
for com in combinations(virus, m): # 바이러스가 퍼질 수 있는 조합
    answer = min(answer, bfs(com))

print(answer if answer != maxsize else -1)
    

설명

bfs 내에 빈칸을 세어주는게 핵심이다.

이 부분을 안해줘서 계속 비활성 바이러스를 업데이트 안하고 끝내야 할때 활성 바이러스로 변환시켜 이상한 값이 출력되곤 했는데 처음부터 빈칸의 개수를 세어주고 빈칸이 다 채워지면 종료하도록 하니 문제가 해결됐다.

참고 자료