[SW역량테스트준비] 연구소 3

연구소 3

연구소에 바이러스를 퍼뜨리는데 걸리는 최소시간을 구하는 문제이다.

바이러스를 놓을 수 있는 모든 경우의 수를 만든 후, 각 케이스에 대해 bfs로 바이러스를 퍼뜨려서 최소값을 구하면 된다.

• 연구소의 사이즈는 n*n이고, 바이러스의 갯수는 m개이다.

• 바이러스를 놓을 수 있는 칸의 좌표들을 리스트화하여 리스트 v에 저장하자.

• 빈칸(0)의 갯수를 모두 세고, 이를 k라고 하자. 이 값은 바이러스를 퍼트려야하는 총 개수가 된다.

• 조합을 이용해 m개의 바이러스를 후보칸에 둔다. 이때 리스트 v를 활용하여, 바이러스를 놓은 칸의 좌표를 큐에 넣는다.

• bfs를 통해 바이러스를 퍼트린다. 감염시킬 때마다, 감염시킨 칸의 개수를 세고, 감염시간을 계속 업데이트 해준다.

• 감염은 (0)만 가능하지만, (2) 가 있는 곳으로도 감염이 가능하다.

• bfs가 종료된 후, 감염시킨 칸의 갯수와 k의 갯수가 동일한지 확인한다.

• 만약 비교한 값이 같고, 걸린 시간이 최소라면, 정답으로 업데이트 한다.

• 모든 경우의 수에 대하여 bfs를 돌려본다.

---

code

from collections import deque
from sys import stdin
import sys
sys.stdin = open('input.txt')

n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(n)]
q,v,k = deque(),[],0
select = [False]*10

def init():
    global k
    for i in range(n):
        for j in range(n):
            if a[i][j]==2:
                v.append((i,j))
            if a[i][j]==0:
                k+=1

def bfs(dist):
    global ans
    infect, times = 0,0
    while q:
        x,y = q.popleft()
        for dx,dy in (-1,0),(0,-1),(1,0),(0,1):
            nx,ny = x+dx,y+dy
            if nx<0 or nx>=n or ny<0 or ny>=n:
                continue
            # 벽이 아니고, 아직 퍼지지 않은 곳이라면
            if a[nx][ny]!=1 and dist[nx][ny] ==-1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx,ny))
                # 그 중에서도 0이라
                if a[nx][ny] == 0:
                    infect += 1
                    times = dist[nx][ny]
    # 다 퍼졌으면 갱신해주고 아니면 -1이 출력된다.
    if infect == k:
        ans = min(ans,times)

def solve(idx,cnt,d):
    if cnt == m:
        dist = [[-1]*n for _ in range(n)]
        for i in range(d):
            if select[i]:
                x,y = v[i]
                q.append((x,y))
                dist[x][y] = 0  # 활성화 바이러스 안착된 곳이다
        bfs(dist)
        return
    for i in range(idx,d):
        if not select[i]:
            select[i] = True
            solve(i+1,cnt+1,d)
            select[i] = False



ans = 10**9
init()
solve(0,0,len(v))
print(ans if ans!=10**9 else -1)