연구소 2 문제 보러가기
문제를 해결하기 위해 사용한 알고리즘
- BFS
- 조합 (백트래킹으로도 풀 수 있음)
백준 14502 연구실 문제와 유사한 문제로 14502번 연구실 문제에서는 '벽의 개수에 대해서 뽑을 수 있는 모든 경우의 수'를 생각했다면 이번 문제에서는 '바이러스를 놓을 수 있는 모든 경우의 수'에 대해서 생각하는 문제이다.
문제
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.
연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×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 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 5시간이 최소가 되는 방법은 아래와 같고, 5초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.
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
5 - 3 2 3 4 5연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.
입력
첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.
둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.
출력
연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.
핵심 포인트 요약
-
특정 위치에 바이러스 M개를 놓을 것 & 2는 바이러스를 놓을 수 있는 칸이다.
👉 주어진 연구소에서 2는 바이러스를 놓을 수 있는 칸으로 이 중에서 M개를 선택해 놓을 수 있는 모든 경우의 수에 대해서 생각해 봐야한다. -
바이러스는 상하좌우로 인접한 모든 빈칸으로 동시에 복제되며, 1초가 걸린다.
👉 BFS (너비우선탐색) 을 이용하면 될 것같다. 한칸씩 퍼져나갈때 1초가 걸린다 했으므로 너비우선 탐색에서 깊이까지 고려하면 되는 문제이다.
우리가 구현해야 할 핵심 부분
- 바이러스를 놓을 수 있는 모든 경우의 수 (백트래킹 또는 조합으로 구현)
- 바이러스를 퍼뜨리는 행위 + 깊이까지 생각 (BFS로 구현)
- 각각 경우의 수에 대해서 최대 깊이 (최대 걸린시간)을 구한다음 그 중에서 최솟값을 구해야함
코드 & 설명 주석 포함
import sys, copy
from collections import deque
from itertools import combinations
input = sys.stdin.readline
INF = sys.maxsize
# 연구소의 크기(NxN), 놓을 수 있는 바이러스의 개수
N, M = map(int, input().split())
space = [list(map(int, input().split())) for _ in range(N)]
answer = INF
# 바이러스를 놓을 수 있는 칸 (후보)
candidate = []
def init():
for i in range(N):
for j in range(N):
if space[i][j] == 2:
candidate.append((i, j))
if space[i][j] == 1:
space[i][j] = '-'
else:
# 바이러스를 모든 빈 칸에 퍼뜨릴 수 없는 경우를 판단하기 위함
space[i][j] = -1
init()
# 바이러스를 퍼뜨리는 함수
def bfs(que, tmp_space, visited):
dydx = [(0, 1), (1, 0), (-1, 0), (0, -1)]
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]:
if tmp_space[ny][nx] != '-':
tmp_space[ny][nx] = tmp_space[y][x] + 1
visited[ny][nx] = True
que.append((ny, nx))
# 바이러스를 모두 퍼뜨리는데 걸리는 시간을 구함
time = 0
for i in range(N):
for j in range(N):
if tmp_space[i][j] == '-':
continue
# 모든 빈 칸에 바이러스를 못 퍼뜨린 경우
if tmp_space[i][j] == -1:
return sys.maxsize
if tmp_space[i][j] > time:
time = tmp_space[i][j]
return time
# 바이러스를 놓을 수 있는 칸중에서 M개를 선택하는 함수
def select_virus():
global answer
que = deque()
# 조합을 이용하여 M개를 선택
for i in combinations(candidate, M):
visited = [[False]*N for _ in range(N)]
tmp_space = copy.deepcopy(space)
for row,col in i:
que.append((row, col))
tmp_space[row][col] = 0
visited[row][col] = True
answer = min(bfs(que, tmp_space, visited), answer)
select_virus()
if answer == INF:
print(-1)
else:
print(answer)
코드 & 설명 주석 미포함
import sys, copy
from collections import deque
from itertools import combinations
input = sys.stdin.readline
INF = sys.maxsize
N, M = map(int, input().split())
space = [list(map(int, input().split())) for _ in range(N)]
answer = INF
candidate = []
def init():
for i in range(N):
for j in range(N):
if space[i][j] == 2:
candidate.append((i, j))
if space[i][j] == 1:
space[i][j] = '-'
else:
space[i][j] = -1
init()
def bfs(que, tmp_space, visited):
dydx = [(0, 1), (1, 0), (-1, 0), (0, -1)]
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]:
if tmp_space[ny][nx] != '-':
tmp_space[ny][nx] = tmp_space[y][x] + 1
visited[ny][nx] = True
que.append((ny, nx))
time = 0
for i in range(N):
for j in range(N):
if tmp_space[i][j] == '-':
continue
if tmp_space[i][j] == -1:
return sys.maxsize
if tmp_space[i][j] > time:
time = tmp_space[i][j]
return time
def select_virus():
global answer
que = deque()
for i in combinations(candidate, M):
visited = [[False]*N for _ in range(N)]
tmp_space = copy.deepcopy(space)
for row,col in i:
que.append((row, col))
tmp_space[row][col] = 0
visited[row][col] = True
answer = min(bfs(que, tmp_space, visited), answer)
select_virus()
if answer == INF:
print(-1)
else:
print(answer)혹시나 잘못된 부분이 있으면 댓글 부탁드립니다.
