백준(BOJ) 17142 연구소 3(Python)

문제 내용.

 

BFS 문제.

N과 M이 그렇게 크지 않기 때문에, 바이러스를 활성화시킬 수 있는 모든 경우에 대해 BFS를 돌릴 수 있다.

모든 경우 중 칸을 다 채울 수 있으면서 가장 시간이 적게 걸리는 경우를 찾으면 된다.

이 때 주의할 점은, 모든 칸에 "바이러스"가 존재하는 경우를 찾아야 하므로 비활성화된 바이러스를 활성화시키는 경우는 칸을 채운 것으로 간주해선 안 된다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
n,m=map(int,input().split())
L=[list(map(int,input().split())) for i in range(n)]
C=[]
c=0
dx=[0,0,1,-1]
dy=[1,-1,0,0]
for i in range(n):
    for j in range(n):
        if L[i][j]==2:
            C.append([i,j])
        if L[i][j]==0:
            c+=1
visited=[[0]*n for i in range(n)]
ans=100000000
for comb in combinations(C,m):
    for i in range(n):
        for j in range(n):
            visited[i][j]=0
    queue=deque()
    count=0
    for x,y in comb:
        queue.append([x,y,0])
        visited[x][y]=1
    time=0
    while queue and count<c:
        x,y,t=queue.popleft()
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
            if 0<=nx<n and 0<=ny<n and L[nx][ny]!=1 and not visited[nx][ny]:
                visited[nx][ny]=1
                queue.append([nx,ny,t+1])
                if L[nx][ny]==0:
                    count+=1
                time=t+1
    if count==c:
        ans=min(ans,time)
if ans==100000000:
    print(-1)
else:
    print(ans)

문제가 너무 길다.