[문제 바로가기] https://www.acmicpc.net/problem/17142
📌문제 설명
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.
M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.
시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.
연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.입력
첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.
출력
연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.
💡 문제 풀이
연구소 시리즈(?) 문제다.
이전에 풀었던 '연구소 1'과 마찬가지로 BFS + 조합으로 해결하면 된다.
(개인적으로) 문제해결의 가장 큰 어려움으로 느꼈던 것은 비활성화 된 바이러스의 처리였다.
※ 만약, BFS 탐색으로 바이러스를 다 퍼뜨렸음에도 불구하고 비활성화된 바이러스를 탐색하지 않았다고 시간을 소비하면 정답이 나오지 않을 수 있다.
또한, N의 크기가 최대 50이기 때문에 BFS 구현 시 시간초과에 주의해야 했다.
step 1)
'연구소 1' 문제와 마찬가지로 바이러스 좌표를 모두 배열에 담았다.
- virus : 모든 바이러스의 좌표를 담은 배열
그리고 BFS 탐색시 visited를 사용하지 않고 empty 변수를 만들어
바이러스가 퍼뜨릴 수 있는 빈 공간(0)의 개수를 담았다.
BFS 탐색으로 바이러스가 퍼지면 empty-1을 진행할 것이고 만약 empty가 0이면 모든 빈 공간에 바이러스가 퍼진 것이므로 더 이상 진행할 필요가 없다.
step 2)
virus 배열에서 M개의 좌표를 조합으로 선택한 후 큐(queue)에 담아 BFS를 진행한다.
이 때, 비활성화된 바이러스를 신경써줘야 하기 때문에 set()을 이용하여 따로 좌표를 배열에 담아서 함수 인자로 넣어줬다.
최소 이동시간을 구해야하므로 선택한 바이러스 좌표의 값에는 0으로 초기화한다.
조합으로 선택된 각 케이스마다 바이러스가 퍼지는 시간을 비교하기 위해서 time 변수를 만들었다.
→ time 변수에는 현재 바이러스가 퍼지는 시간을 최신화해준다.
step 3)
queue에 담긴 원소가 없을 때 까지 BFS를 진행한다.
4방향으로 탐색하면서 NxN 배열 범위안에 들어오면
조건문으로 다음과 같이 경우를 나눈다.
- 빈 칸(0)이며 좌표가 virus안에 없다면?
NxN배열에서 0인 값은 빈 칸 또는 선택한 바이러스 좌표의 값이다. 따라서 좌표가 virus안에 담겨 있지 않으면 바이러스가 퍼져야 하는 빈 칸을 의미한다. 조건문을 만족하면 아래의 과정을 진행한다.
- 이전 이동시간+1을 해준다.
- time의 값을 최신화한다.
- 해당 좌표를 queue에 담는다.
- 만약 time이 최소 이동시간(answer)보다 같거나 크면 진행을 멈춘다.
- 해당 좌표의 값이 2이며 좌표가 not_activate안에 있다면?
NxN배열에서 2인 값은 이동거리가 2인 칸이거나 비활성화된 바이러스 밖에 없다. 이동거리가 2이면 그대로 진행하면 되지만 비활성화된 바이러스라면 처리를 다르게 해주어야 한다.
-
2-1. empty > 0이라면?
만약, 바이러스가 아직 다 퍼지지 않았음에도 비활성화된 바이러스 칸에 도착한다면 빈 칸에서의 BFS탐색처럼 진행한다.- 이전 이동시간+1을 해준다.
- time의 값을 최신화한다.
- 해당 좌표를 queue에 담는다.
-
2-2. empty == 0이라면?
바이러스가 모두 퍼졌음에도 비활성화된 바이러스에 불필요하게 접근하려는 경우이기 때문에 굳이 이동시간+1을 해줄 필요가 없다.- 이전 이동시간과 같은 값을 넣어준다.
코드는 다음과 같다.
import sys
from itertools import combinations
from collections import deque
from copy import deepcopy
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs(virus, not_activate, matrix, empty):
global answer
for r, c in virus:
matrix[r][c] = 0
queue = deque(virus)
time = 0
while queue:
if not empty: break
if time >= answer: break
r, c = queue.popleft()
for idx in range(4):
nr = r + d[idx][0]
nc = c + d[idx][1]
if 0 <= nr < N and 0 <= nc < N:
if not matrix[nr][nc] and (nr, nc) not in virus:
matrix[nr][nc] = matrix[r][c] + 1
time = matrix[r][c] + 1
queue.append((nr, nc))
empty -= 1
if matrix[nr][nc] == 2 and (nr, nc) in not_activate:
if empty:
matrix[nr][nc] = matrix[r][c] + 1
time = matrix[r][c] + 1
queue.append((nr, nc))
else:
matrix[nr][nc] = matrix[r][c]
if not empty:
answer = min(answer, time)
N, M = map(int, input().split())
empty = 0
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
virus= []
for r in range(N):
for c in range(N):
if matrix[r][c] == 2:
virus.append((r, c))
elif not matrix[r][c]:
empty += 1
answer = int(1e9)
for li in combinations(virus, M):
bfs(li, list(set(virus) - set(li)), deepcopy(matrix), empty)
print(answer) if answer != int(1e9) else print(-1)비활성화 바이러스 처리에 관한 조건을 제대로 읽지 않아서 시간을 엄청 낭비했다...
쉬운 문제라도 곰꼼히 읽고, 어떻게 해결할 것인지 적고난 후 코딩하자...
