[python] BOJ 백준 17142: 연구소3

1. 문제  

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

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

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

2. 입력   

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

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

3. 출력   

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

4. 해결방법   

이 문제는 조합을 활용한 BFS 알고리즘이다. 바이러스를 퍼뜨리는 부분은 DFS나 BFS 알고리즘을 사용하여 구현해줄 수 있다. 큐에 바이러스가 있는 위치를 넣어준 다음, 상하좌우로 움직이면서 아직 방문하지 않은 곳들 중에 비활성바이러스가 있거나 빈칸일 경우에 바이러스를 퍼뜨려주면된다. 하지만 이때 활성화 바이러스인 부분은 문제에서 m개를 택하라고 하였으므로, 조합을 이용하여 모든 경우의 수를 구해주어야한다. 삼성 코딩테스트에서 itertools의 사용은 되지않으므로 해당 조합을 구하는 함수는 따로 작성을 해주어야한다. 

1) BFS 함수: 큐에 활성화 바이러스의 좌표들을 넣어놓은 다음, 하나씩 꺼내면서 상하좌우를 탐색하면된다. 하지만 이때 주의할점은 우리가 구해야하는 것은 최소시간이라는 점이다. 최소시간을 구하기 위해서는 큐에 담아 pop하는 바이러스들이 같은 턴에 이루어져야한다는 것을 의미한다. 따라서 while문안에 for문을 작성하여 for문을 돌릴 당시에 큐 길이 만큼 pop을 같이 해주어야 한 타임으로 계산을 할 수 있다. 이 방법이 귀찮다면, 큐에 넣어줄때 x,y좌표 이외에 바이러스에 감염된 시간을 같이 넣어서 그것에 +1을 한값을 큐에 넣어주면된다. 2가지의 방법중 편한 방법을 이용하면된다. 다만 이미 구한 최소시간보다 더 많은 시간이 걸리는 중이거나, 빈공간이 없으면 즉시 큐 탐색을 종료하여 효율성을 높여준다. 빈 공간이 없는 경우에만 시간을 리턴하게 해주어 최소시간만을 업데이트할 수 있게끔 해준다. 

이 문제에서 조금더 쉬운버전은 풀어보려면 연구소1 을 풀면된다. 해당 링크를 첨부해놓겠다. 

2022.03.30 - [Coding Test/BaekJoon] - [python] BOJ 백준 14502: 연구소

[python] BOJ 백준 14502: 연구소

 

5) 구현코드   

from collections import deque 
from itertools import combinations


dx, dy = [-1, 1, 0, 0], [0 , 0, -1, 1]
time = 1e9 #최소시간
 

#바이러스 퍼뜨리기 
def bfs(virus, min_time, leftArea):
    global time 
    queue = deque(virus) #바이러스 큐 
    time_val = 0 #바이러스가 퍼진 시간 
    visited = [[False] * n for _ in range(n)] #방문한 자리 
    #바이러스가 있는 곳은 이미 방문처리 
    for x, y in virus:
        visited[x][y] = True
 
    while queue: #바이러스를 돌면서 
        if not leftArea: #빈공간이없으면 
            break #탈출
        time_val += 1 #시간증가 
        if time_val >= min_time: #이미 최소시간보다 더 시간걸리면 
            return 1e9 #탈출 
 
        for _ in range(len(queue)): #한 타임내에 돌아야하므로 
            x, y = queue.popleft() #바이러스 위치 
            for i in range(4): #상,하,좌,우
                nx, ny = x + dx[i], y + dy[i]
                if 0 <= nx < n and 0 <= ny < n: #그래프 내에 있고 
                    #비활성화 바이러스 이거나 빈곳일 경우 (방문하지 않았다면)
                    if graph[nx][ny] != 1 and not visited[nx][ny]:
                        visited[nx][ny] = True #방문처리 
                        queue.append((nx, ny)) #큐에 넣어주기 
                        if graph[nx][ny] == 0:  
                          leftArea -= 1 #남은 빈 공간 업데이트 
 
    if not leftArea:
        return time_val
    else:
        return INF
 
 
 
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
virusList = []
 
left = 0
# 바이러스가 있으면 위치 저장 및 빈 공간 체크
for i in range(n):
    for j in range(n):
        if graph[i][j] == 2:
            virusList.append([i, j]) #바이러스가 있는 공간 
        if graph[i][j] == 0: 
            left += 1 #빈공간 
 
# 바이러스 N개 중 m개를 선택 nCm
for virus in combinations(virusList, m):
    time = min(time, bfs(virus, time, left))
 
# 이동 못 할 경우 -1 출력, 만약 도착 했으면 값을 출력
if time == 1e9:
    print(-1)
else:
    print(time)

 

⭐️난이도:  골드 4⭐️ 

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

17142번: 연구소 3