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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
| import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Point {
int x, y;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
static int N, M, map[][];
static List<Point> ableVirus;
static int res;
public static void main(String[] args) throws Exception {
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];
ableVirus = new ArrayList<Point>();
int blankCnt = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 0) { // 빈 칸
blankCnt++;
} else if (map[i][j] == 1) { // 벽
map[i][j] = -1; // 벽은 -1로 바꿔줌
} else if (map[i][j] == 2) { // 바이러스가 들어갈 수 있는 빈 칸
ableVirus.add(new Point(i, j)); // 바이러스가 올 수 있는 빈 칸 추가
map[i][j] = 0; // 빈 칸 0으로 바꿔줌
blankCnt++; // 빈 칸 카운트
}
}
} // input end
res = Integer.MAX_VALUE;
if (blankCnt == M) { // 빈 칸이랑 바이러스 수 같으면 더 퍼트릴 필요 없음
res = 0;
} else {
ArrayList<Point> virus = new ArrayList<>();
comb(0, 0, virus);
}
if (res == Integer.MAX_VALUE)
res = -1;
System.out.println(res);
}
// 바이러스 놓을 위치 M개 고르는 함수
private static void comb(int start, int cnt, ArrayList<Point> virus) {
if (cnt == M) { // 바이러스 놓을 위치 M개를 고르면
int[][] copy_map = BFS(copyArr(map), virus);
res = Math.min(res, check(copy_map));
return;
}
for (int i = start; i < ableVirus.size(); i++) {
virus.add(ableVirus.get(i));
comb(i + 1, cnt + 1, virus);
virus.remove(virus.size() - 1);
}
}
// 바이러스 퍼진 후에 빈 칸이 있는지 확인하고 퍼지는데 걸린 시간을 반환하는 함수
private static int check(int[][] map) {
int sec = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 0) { // 빈 칸이 있으면 -1
return Integer.MAX_VALUE;
} else {
sec = Math.max(sec, map[i][j]);
}
}
}
return sec;
}
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
// 바이러스 퍼트리는 함수
private static int[][] BFS(int[][] copy_map, ArrayList<Point> virus) {
Queue<Point> queue = new LinkedList<>();
for (int i = 0; i < M; i++) {
queue.offer(virus.get(i));
copy_map[virus.get(i).x][virus.get(i).y] = -10; // 초기 바이러스가 있는 곳
}
while (!queue.isEmpty()) {
Point cur = queue.poll();
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
// 범위 체크
if (nx < 0 || nx >= N || ny < 0 || ny >= N)
continue;
// 벽이거나 초기 바이러스가 있는 곳이면 패스
if (copy_map[nx][ny] != 0)
continue;
queue.offer(new Point(nx, ny));
if (copy_map[cur.x][cur.y] == -10) {
copy_map[nx][ny] = 1;
} else {
copy_map[nx][ny] = copy_map[cur.x][cur.y] + 1;
}
}
}
return copy_map;
}
private static int[][] copyArr(int[][] origin) {
int[][] copy = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
copy[i][j] = origin[i][j];
}
}
return copy;
}
}
|
