(삼성기출) 백준 17142번 - 연구소 /Wanna Be 컴잘알

문제 출처 : https://www.acmicpc.net/problem/17142

17142번: 연구소 3

-문제-

 

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 2 0 1 1 0 1 0 0 0 0 0 2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

* 6 5 4 - - 2 5 6 - 3 - 0 1 4 - - 2 - 1 2 3 - 2 1 2 2 3 2 2 1 0 1 - - 1 - 2 1 2 3 4 0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2 1 2 - 3 - 0 1 2 - - 2 - 1 2 3 - 2 1 2 2 3 3 2 1 0 1 - - 4 - 2 1 2 3 4 * - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

 

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

 

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

 

-설명-

 

1. huboList 리스트에 바이러스의 y,x좌표를 저장한다. 

2. solve()함수를 사용해 dfs방식으로 huboList에 있는 바이러스 중 M개를 선택한다.

3. 선택된 바이러스를 기준으로 bfs를 실시한다.

4. 단, 문제의 조건을 보면 모든 연구소를 다 방문할 필요는 없다. 모든 빈 칸이 바이러스가 되면 되므로, 아직 방문하지 않은 비활성화 바이러스가 존재해도 무관한다. 따라서 현재 연구소에 빈칸이 몇 개 있는지 확인한다. -> beanCnt

5. bfs를 수행하면서 beanCnt와 현재 빈칸을 감염시킨 수가 같아지면 종료한다.

 

-코드-

import sys
from collections import deque
input = sys.stdin.readline

# 0:빈 칸, 1: 벽, 2: 바이러스
# 활성바이러스가 비활성 바이러스가 있는 칸 가면 바이러스 활성화됨
# m개의 바이러스 활성화
# 연구소 크기 N, 바이러스 개수 M

minValue = -1

def bfs(huboList,vector,laborMap, beanCnt):
    dq = deque()
    N = len(laborMap)
    check = [[False for _ in range(N)] for _ in range(N)]
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    cnt = 0
    for i in vector: 
        check[huboList[i][0]][huboList[i][1]] = True
        dq.append(huboList[i])
    
    beanCnting = 0
    stopFlag = False

    while len(dq)>0:
        loop = len(dq)
        for _ in range(loop):
            obj = dq.popleft()
            curY = obj[0]
            curX = obj[1]
            for k in range(4):
                nextY = curY+dy[k]
                nextX = curX+dx[k]
                if nextY>=0 and nextY<N and nextX>=0 and nextX<N and check[nextY][nextX] == False and laborMap[nextY][nextX] !=1:
                    check[nextY][nextX] = True
                    if laborMap[nextY][nextX] == 0:
                        beanCnting +=1
                    dq.append([nextY,nextX])
                
            if beanCnt == beanCnting:
                stopFlag= True
                break
        
        cnt+=1
        if stopFlag:
            break
    
    global minValue
    if stopFlag:
        if minValue == -1:
            minValue = cnt
        else:
            minValue = min(minValue, cnt)


def solve(end,standard, check, cnt, input, huboList, vector,laborMap, beanCnt):
    if end==cnt:
        bfs(huboList,vector,laborMap, beanCnt)
        return
    for i in range(standard, len(input)):
        if check[i] == False:
            check[i] = True
            vector.append(input[i])
            solve(end, i, check, cnt+1, input, huboList, vector,laborMap, beanCnt)
            vector.pop()
            check[i] = False


def solution(laborMap,huboList,N,M, beanCnt):
    check = [False for _ in range(len(huboList))]
    input = [i for i in range(len(huboList))]
    solve(M,0,check,0,input, huboList, [],laborMap, beanCnt)

if __name__ == "__main__":
    N,M = map(int,input().split())
    laborMap = []
    huboList = []
    beanCnt = 0
    for row in range(N):
        temp = list(map(int, input().split()))
        for col in range(len(temp)):
            if temp[col] == 2: huboList.append([row,col])
            elif temp[col] == 0:
                beanCnt +=1
        laborMap.append(temp)
    
    if beanCnt > 0:
        solution(laborMap,huboList,N,M, beanCnt)
    else:
        minValue = 0
    print(minValue)