[백준/17141/파이썬] 연구소 2

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

17141번: 연구소 2

Problem

• 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.
• 연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

조건

• 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
• 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 
• 첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

SOL

벽을 세우는게 아니라, 바이러스가 될 수 있는 후보지에서 m개를 뽑아서 바이러스를 터뜨리는 경우이다.

m<=10이므로, 10C5 =252 가지밖에 되지않으므로, BFS로 탐색을 한다고 해도 충분히 가능하다.

 

크게 3가지 부분으로 나눌 수 있을거 같다.

1. 바이러스 후보지를 선택하는 방법
2. 바이러스를 퍼뜨리는 방법
3. 바이러스를 퍼뜨리고 난 후, 최소시간을 구하는 방법

바이러스 후보지를 선택하는 방법

바이러스 후보지를 선택하려면, 우선 "2"가 있는 곳에서 m개를 뽑아내야한다.

• "2"가 있는 곳을 virus에 index 정보를 저장해놓는다.
• 그리고, virus안에 index들을 선택하기 위해서, mapping을 위한 index 배열을 따로 만들어준다. (select)
• board=0인 이유는, 선택되지 못한 곳에도 바이러스가 퍼져야하기 때문이다. 그래서 그때마다 처리해주기 귀찮아서 다 0으로 만들어버렸음. (어차피, virus가 퍼지는건 visited라는 배열에 기록할거기 때문)

for i in range(N):
    for j in range(N):
        if board[i][j]==2:
            virus.append((i,j))
            board[i][j]=0
select =[0 for _ in range(10)]

다음은 , 후보들 중에, 우리가 봐야하는 조합을 구현하면 된다. 조합을 구현할 때, 재귀적으로 직접 구현도 가능하고, 내장되어있는 기능인 combination을 사용하여도 무방하다.우선, DFS로 하나하나 다 재귀적으로 구하는 경우로 구현할거임!

# 탈출 지점, cnt==M이 되는 경우
if cnt==M:
	##탐색하기 

## 모든 조합을 재귀적으로 구현
for i in range(idx,len(virus)):
	if select[i]:
    	continue
    select[i] =1
    select_virus(i+1,cnt+1)
    select[i] =0

의사코드를 쓰자면, 위와같이 적을 수 있다.

 

바이러스 퍼뜨리기 (탐색하기)

사실 이 부분은 , 워낙 많이 구현했던 부분이라, 어려움 없이 구현할 수 있었다.

#if cnt==M인 경우
	dq=deque()
        visited=[[-1]*N for _ in range(N)]
        for i in range(len(virus)):
            if select[i]: # select[i] ,즉 i번째 인덱스가 선택된 경우만 뽑아서 넣어주기.
                y,x=virus[i][0],virus[i][1]
                dq.append((y,x))
                visited[y][x] =0
        solve()

#solve() 함수의 의사코드
	while dq:
        y,x = dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if (0<=ny<N and 0<=nx<N) and visited[ny][nx]==-1:
                if board[ny][nx] ==0:
                    visited[ny][nx] = visited[y][x] +1
                    cnt=max(cnt,visited[ny][nx])
                    dq.append((ny,nx))

 

퍼뜨리고 난 후, 최소시간 구하기

• 퍼뜨리고 난 후, 문제에서 바이러스가 어떻게 놔도 퍼지지 못하는 곳이 있으면 print -1을 해야하므로, 그거 먼저 검사해준다.
• 그리고, 각 바이러스를 놓는 경우의 수에 따라, max값을 찾아주고, 그 중에 최솟값을 구해야 하기 때문에,
• ans = min(ans,cnt)를 해주면 된다!

    for i in range(N):
        for j in range(N):
            if board[i][j] ==0 and visited[i][j] ==-1:
                cnt=sys.maxsize
    ans=min(ans,cnt)

 

전체코드

# 연구소 2
from collections import deque
from itertools import combinations
import sys
input = sys.stdin.readline
N,M =map(int,input().split())
board=[list(map(int,input().split())) for _ in range(N)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
virus =[]

for i in range(N):
    for j in range(N):
        if board[i][j]==2:
            virus.append((i,j))
            board[i][j]=0
#print(virus)
#탐색 바이러스를 터뜨린다
def solve():
    global visited,dq,ans
    cnt=0
    while dq:
        y,x = dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if (0<=ny<N and 0<=nx<N) and visited[ny][nx]==-1:
                if board[ny][nx] ==0:
                    visited[ny][nx] = visited[y][x] +1
                    cnt=max(cnt,visited[ny][nx])
                    dq.append((ny,nx))
    # 최솟값 찾기
    for i in range(N):
        for j in range(N):
            if board[i][j] ==0 and visited[i][j] ==-1:
                cnt=sys.maxsize
    ans=min(ans,cnt)

# 퍼뜨릴 바이러스를 정한다.
def select_virus(idx,cnt):
    global dq,visited,ans
    if cnt==M:
        dq=deque()
        visited=[[-1]*N for _ in range(N)]
        for i in range(len(virus)):
            if select[i]:
                y,x=virus[i][0],virus[i][1]
                dq.append((y,x))
                visited[y][x] =0
        solve()
        return
    for i in range(idx,len(virus)):
        if select[i]:
            continue
        select[i]=1
        select_virus(i+1,cnt+1)
        select[i]=0

select =[0 for _ in range(10)]
ans=sys.maxsize
select_virus(0,0)
print(ans) if ans != sys.maxsize else print(-1)

내일은 combination을 이용해서 풀어보고 풀이를 추가해보겠다!