연구소 3 문제 보러가기
문제를 해결하기 위해 사용한 알고리즘
- BFS
- 백트래킹 (조합으로도 풀 수 있음)
백준 17141 연구소2 문제와 유사한 문제로 해당 문제에서는 비활성화와 활성화 바이러스를 어떻게 처리할 것인지에 대한 문제이다.
문제
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 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 2M = 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초가 걸린다.
- 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
👉 활성화 바이러스가 비활성화 바이러스를 만난다는 것은 그대로 통과한다는 의미. (지나갈수 있다는 의미) 원래 비활성화 였던 바이러스는 스스로 퍼져나갈 수 있는게 아님 즉, 활성 상태 바이러스가 비활성 상태인 바이러스를 타고 넘어가서 이동할 수 있음
코드 & 설명 주석 포함
from collections import deque
import sys, copy
input = sys.stdin.readline
INF = sys.maxsize
# 연구소의 크기(NxN), 활성화할 바이러스 M개 선택
N, M = map(int, input().split())
space = [list(map(int, input().split())) for _ in range(N)]
answer = INF
# 벽은 '-', 바이러스 위치는 '*'(비활성), 나머지 -1로 space(배열)를 초기화
# 바이러스의 위치가 담긴 큐(후보)를 return하는 함수
def init():
virus = deque()
for i in range(N):
for j in range(N):
# 벽일 경우
if space[i][j] == 1:
space[i][j] = '-'
# 만약 바이러스가 들어갈 수 있는 자리라면
elif space[i][j] == 2:
space[i][j] = '*' # 아직 선택한 상태가 아니므로 비활성 상태로 표시
virus.append((i, j))
else: # 벽도 아니고 바이러스도 아닌 경우
space[i][j] = -1
# 바이러스가 모든 빈칸에 퍼졌나 안퍼졌나 판단하기 위함
return virus
# 바이러스를 활성화 시킬수 있는 후보 좌표(위치)
candidate = init()
def bfs(sol):
dydx = [(0, 1), (1, 0), (-1, 0), (0, -1)]
visited = [[False]*N for _ in range(N)]
tmp_space = copy.deepcopy(space)
que = copy.deepcopy(sol)
time = 0
# 활성 바이러스는 0으로 표시
for y,x in que:
visited[y][x] = True
tmp_space[y][x] = 0
while que:
y, x = que.popleft()
for dy,dx in dydx:
ny = y + dy
nx = x + dx
if 0<=ny<N and 0<=nx<N and not visited[ny][nx] and tmp_space[ny][nx] != '-':
# 빈칸이라면
if tmp_space[ny][nx] == -1 :
tmp_space[ny][nx] = tmp_space[y][x] + 1
time = max(time, tmp_space[ny][nx])
# 비활성화 상태의 바이러스를 만난다면 통과해야하기 때문에 시간은 1초 늘려줘야하지만 갱신은 하지 않는다. (2차원 평면상에서의 한계)
elif tmp_space[ny][nx] == '*':
tmp_space[ny][nx] = tmp_space[y][x] + 1
visited[ny][nx] = True
que.append((ny, nx))
# -1이 존재한다는 것은 모든 빈 칸에 바이러스를 퍼뜨릴 수 없었다는 의미
for i in range(N):
for j in range(N):
if tmp_space[i][j] == -1:
time = sys.maxsize
return time
return time
# 바이러스를 활성화 시킬 M개를 선택하는 함수 (백트래킹으로 구현)
def select_virus(sol, level):
global answer
# 활성화 시킬 M개를 정했다면
if len(sol) == M:
answer = min(bfs(sol), answer) # bfs수행
return
for i in range(level, len(candidate)):
sol.append(candidate[i])
select_virus(sol, i+1)
sol.pop()
select_virus(deque(), 0)
if answer == INF:
print(-1)
else:
print(answer)
보충 설명
if 0<=ny<N and 0<=nx<N and not visited[ny][nx] and tmp_space[ny][nx] != '-':
if tmp_space[ny][nx] == -1 :
tmp_space[ny][nx] = tmp_space[y][x] + 1
# time을 갱신할때 활성 상태에서만 고려해야함
time = max(time, tmp_space[ny][nx])
elif tmp_space[ny][nx] == '*':
tmp_space[ny][nx] = tmp_space[y][x] + 1
visited[ny][nx] = True
que.append((ny, nx))활성화와 비활성화 바이러스를 처리하는 부분에서 주의해야 할점
- 활성화된 바이러스가 다 퍼져야 하는게 아니라 활성화여부는 상관없이 바이러스만 퍼져있으면 됨
- 모든 칸에 바이러스가 퍼지는 최소 시간을 구할 때, 활성 상태 바이러스가 비활성 상태인 바이러스 자리까지 도달하는 데에 걸리는 시간은 고려하지 않음, 즉. time을 갱신할 때에는 활성 상태에서만 고려해야함
반례 참고
5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 0 0 2 0
1 1 1 1 1
answer 2혹시나 잘못된 부분이 있으면 댓글 부탁드립니다.
