BOJ 17142 연구소 3
https://www.acmicpc.net/problem/17142
문제
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 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 2
M = 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
7 3 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 2
예제 출력 1
4
예제 입력 2
7 3 2 0 2 0 1 1 0 0 0 1 0 1 2 0 0 1 1 2 1 0 0 2 1 0 0 0 0 2 0 0 0 2 0 1 1 0 1 0 0 0 0 0 2 1 0 0 2 0 2
예제 출력 2
4
… 이하 예제 생략
코드
이전 BOJ 17141 연구소 2 문제와 거의 유사하다.
다른 점은 초기 바이러스 후보 중 선택되지 않은 바이러스는 비활성화 상태인 바이러스가 되는 것인데, 이 부분은 최소 확장 시간 계산 전에 초기 비활성화 상태인 바이러스의 확장 시간을 0으로 초기화하고 계산하면 되는 부분이다.
그렇기 때문에 코드 변화가 거의 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N, M, answer = Integer.MAX_VALUE;
static int[][] map;
static ArrayList<Point> viruses = new ArrayList<>(); // 초기 바이러스가 놓일 수 있는 위치들
static Point[] selected; // 선택된 M개의 바이러스 위치
static int[] dirRow = {1, -1, 0, 0}, dirCol = {0, 0, 1, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][N];
selected = new Point[M];
// map에서 벽은 MIN_VALUE, 나머지 공간은 MAX_VALUE로 초기화
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
String input = st.nextToken();
if(input.equals("1")) map[i][j] = Integer.MIN_VALUE;
else if (input.equals("2")) {
viruses.add(new Point(i, j));
map[i][j] = Integer.MAX_VALUE;
}
else map[i][j] = Integer.MAX_VALUE;
}
}
dfs(0, 0);
System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
}
// 초기 바이러스 위치 선택은 DFS(조합), 바이러스의 확장은 BFS 사용
static void dfs(int level, int idx) {
// 초기 바이러스의 위치 선택이 끝나면(level == M) BFS로 바이러스 확장
if(level == M) {
Queue<Point> queue = new LinkedList<>();
// 초기 바이러스의 위치를 queue에 offer
for (Point virus: selected) {
map[virus.x][virus.y] = 0;
queue.offer(virus);
}
while (!queue.isEmpty()) {
Point check = queue.poll();
// 확인하는 바이러스의 상하좌우 각각의 위치가 map의 범위 안에 있고
// 해당 위치의 값(확장 시간)이 확인하는 바이러스의 값 + 1보다 클 때, queue에 offer
for (int i = 0; i < dirRow.length; i++) {
int newRow = check.x + dirRow[i], newCol = check.y + dirCol[i];
boolean isInside = 0 <= newRow && N > newRow && 0 <= newCol && N > newCol;
if(isInside && map[newRow][newCol] > map[check.x][check.y] + 1) {
map[newRow][newCol] = map[check.x][check.y] + 1;
queue.offer(new Point(newRow, newCol));
}
}
}
// 초기에 비활성화 상태인 바이러스의 확장 시간을 0으로 만들어준다.
for (Point virus: viruses)
map[virus.x][virus.y] = 0;
answer = Integer.min(answer, calMinTime());
reduce();
return;
}
for (int i = idx; i <= viruses.size() - M + level; i++) {
selected[level] = viruses.get(i);
dfs(level + 1, i + 1);
}
}
// 벽을 제외한 나머지 값을 MAX_VALUE로 초기화
static void reduce() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(map[i][j] >= 0) map[i][j] = Integer.MAX_VALUE;
}
}
}
static int calMinTime() {
int minTime = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
minTime = Integer.max(minTime, map[i][j]);
}
}
return minTime;
}
}