백준 17142 - 연구소 3 (Python)

https://acmicpc.net/problem/17142 

17142번: 연구소 3

연구소 2와 비슷해보이긴 하지만 난이도는 꽤 차이가 나는 문제였다.

비활성화 바이러스를 어떻게 처리할지가 고민이었는데, 결국 0인 빈 칸을 얼마나 바꿨는지를 기록했다.

즉, 비활성화는 지나가며 q에 추가하지 않지만 0인 빈 칸을 바꾼 count에는 포함시키지 않았다.

그리고 비활성화 바이러스와 벽만 있는 경우에는 바로 0을 출력했다. 

다른 부분은 연구소 2와 모두 동일했다.

import sys,itertools,copy
from collections import deque
input=sys.stdin.readline
N,M=map(int,input().split())
lab=[]
viruses=set()
dy=[0,0,1,-1]
dx=[1,-1,0,0]
zeros=0 # 0의 개수 세기
ans=10**6

for i in range(N):
    cur=list(map(int,input().split()))
    for j in range(N):
         if cur[j]==2:
             viruses.add((i,j,0))
             cur[j]=3 # 비활성화 바이러스는 3으로 표기
         elif cur[j]==0:
             zeros+=1
    lab.append(cur)
if not zeros: # 감염시킬 수 있는 공간이 없으면 바로 종료
    print(0)
    exit(0)

def spread(cur_viruses):
    cur_lab=copy.deepcopy(lab)
    for virus in cur_viruses:
        cur_lab[virus[0]][virus[1]]=2
    cur_viruses=deque(cur_viruses)
    cnt=0
    while cur_viruses:
        y,x,t=cur_viruses.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if 0<=ny<N and 0<=nx<N:
                if cur_lab[ny][nx]==0:
                    cur_lab[ny][nx]=2
                    cnt += 1 # cnt는 0의 개수.
                    if cnt == zeros:
                        return t+1
                    cur_viruses.append((ny,nx,t+1))
                if cur_lab[ny][nx]==3:
                    cur_lab[ny][nx]=2
                    cur_viruses.append((ny,nx,t+1))

    return 10**6


virus_combinations=itertools.combinations(viruses,M)
for i in virus_combinations:
    ans=min(ans,spread(i))

if ans==10**6:
    print(-1)
else:
    print(ans)