[acmicpc] 17142. 연구소 3(python)

combinations와 bfs사용

import sys,copy
from collections import deque
from itertools import combinations
input=sys.stdin.readline
dirs=[(1,0),(0,1),(-1,0),(0,-1)]
N,M=map(int,input().split())
arr=[]
virus=[]
empty=0
for i in range(N):
    tmp=list(map(int,input().split()))
    new=[]
    for j in range(len(tmp)):
        if tmp[j]==1: new.append('-')
        elif tmp[j]==2:
            new.append('*')
            virus.append((i,j))
        else:
            empty+=1 # 빈칸 개수 세기
            new.append(tmp[j])
    arr.append(new)
    
viruses=list(combinations(virus,M))
answer=2500

#bfs
for virus in viruses:
    arrs=copy.deepcopy(arr)
    time,cnt=0,0
    for v in virus:
        arrs[v[0]][v[1]]=1
    new=deque(virus)
    while new:
        cur=new.popleft()
        for i in range(4):
            nr,nc=cur[0]+dirs[i][0],cur[1]+dirs[i][1]
            if nr<0 or nr>=N or nc<0 or nc>=N: continue
            if arrs[nr][nc]==0:
                arrs[nr][nc]=arrs[cur[0]][cur[1]]+1
                new.append((nr,nc))
                time=arrs[nr][nc]
                cnt+=1
            if arrs[nr][nc]=='*':
                arrs[nr][nc] = arrs[cur[0]][cur[1]] + 1
                new.append((nr, nc))
    if empty==cnt: # 빈칸을 다 지나갔는지 체크
        answer=min(answer,time-1)
        
if answer==2500: print(-1) # 빈칸을 다 못 지나갔으면
elif answer==-1: print(0) # 빈칸이 아예 없다면
else: print(answer)

---

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

17142번: 연구소 3