[백준/17142/파이썬] 연구소 3

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

17142번: 연구소 3

Problem

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

조건

• 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
• 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.
• 첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.
• 둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

SOL

생각보다 엄 -청 까다로웠던 문제다. 아래의 두 테스트 케이스를 통과하는데 애를 먹은 문제다.

4 2 
0 1 1 0
2 1 1 2
2 1 1 2
0 1 1 0
output =2 

5 1 
2 2 2 2 2
2 1 1 1 1
2 2 1 1 1
2 1 1 1 1
2 2 2 2 0

output =1

 

처음에는 , 자신있게 통상적인 BFS처럼 virus 위치 저장해주고, BFS를 돌리는 형식으로 구현하였다.

이때, maps[ny][nx]가 2이냐, 0이냐에 따라서 따로 처리를 해줬는데,  0이면 visited에 기록된 거리 +1을 그대로 해주고, 2이면 visited의 거리는 변함 없이 기록을 해주는걸로 처리했다. (조합의 수는 재귀적으로 구현했음!)

하지만, 이렇게 처리하면, 4 2의 testcase는 통과를 하지 못했음.( 1이 출력됨)

 

바이러스가 만나서 , 다른 바이러스가 활성화 되는 경우에 처리를 여러방면으로 시도해봤지만, 2개의 테스트케이스를 모두 통과하는 경우는 결국 구현하지 못했다. (ㅜㅜ)

 

그래서 ,블로그들을 보게되었고 , 정말 내가 바보같았음을 깨달아버렸따. 단순히 변수를 하나 따로 선언해서, 그곳에 저장하는 방법을 사용하면 되는거였다. (안에서 해결할려고 했는데, 변수를 선언하면 되는 문제였음..)

 

deque와 함께, dist를 일단 저장하고 (visited는 방문 배열로만 사용하자) , 따로 변수 1개를 두어서 다음 방문하는 곳이  0이냐 2이냐에 따라서 처리를 해주고, return을 해주면 간단하게 해결되는 문제이다.

 

0인 경우

• 변수에 Dist +1 값을 저장해준다.

2인 경우

• 변수에는 아무런 값을 저장하지 않고, 넘어간다. (대신, 이때도 deque에는 d +1를 해줘야한다. 왜냐하면, 위의 (4 2) 테스트케이스 처럼 "2"로 인해서 비활성 ->활성으로 바뀌는 동안에도 시간은 흐르기 때문이다)

 

다 끝나고 return 변수 를 해준다.

 

combination은 내장 툴을 함께 사용해보았다. (재귀적으로 구현이 가능하지만, 있는거 한번 써봤다. deque에서 추가하는 과정에서, append를 쓰면, combination의 경우가 다 한개로 묶여서 들어가기 때문에, 객체 그대로 추가하는 방법인 extend를 써서 추가해줬다.)

 

from collections import deque
from itertools import combinations
from copy import deepcopy
import sys
input = sys.stdin.readline

N,M =map(int,input().split())
maps=[]
virus=[]

dy=[1,0,-1,0]
dx=[0,1,0,-1]

for i in range(N):
    a= list(map(int,input().split()))
    for j in range(N):
        if a[j] ==2:
            virus.append((i,j,0))
    maps.append(a)
# 바이러스가 퍼졌는지 check 하는 함수
def check_maps(maps):
    for i in range(N):
        for j in range(N):
            if maps[i][j]==0:
                return -1
    return 0

def bfs(start,maps):
    visited=[[0 for _ in range(N)] for _ in range(N)]
    maps=deepcopy(maps)
    dq=deque()
    dq.extend(start)
    
    cnt=0
    while dq:
        y,x,d=dq.popleft()
        visited[y][x] = 1
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if (0<=ny<N and 0<=nx<N) and not visited[ny][nx] and maps[ny][nx] !=1:
                visited[ny][nx] =1
                if maps[ny][nx] ==0:
                    maps[ny][nx] =2
                    cnt=d+1
                dq.append((ny,nx,d+1))
    val = check_maps(maps)
    #print(maps,val,cnt)
    if val==0:
        return cnt
    else:
        return -1

time=sys.maxsize
candidates=list(combinations(virus,M))

for combi in candidates:
    #print(combi)
    res=bfs(combi,maps)
    if time>res and res != -1:
        time=res

print(time) if time != sys.maxsize else print(-1)