* 전체 2로 표현되어있는 지점들의 개수를 K개라고 할 때 이중 M개를 순서 없이 활성화 시키므로 kCm의 조합을 찾는 것이 첫번째 임무 - 따라서 맵을 읽는 과정에서 바이러스 지점들의 목록을 만들어준다. - 또한 아직 오염되지 않은 지점 즉 0인 지점도 따로 관리한다. * 이제 선택된 m개의 바이러스가 주변으로 전파됨 --> BFS등으로 사방 탐색 시행 * 최종 목표는 바이러스가 전체로 전파되는 최소 시간(depth)를 출력하는 것 * 전염이 완료되는 시점을 파악하기 위해 먼저 오염되지 않은 영역들을 카운트 해놓자 - 지도상에서 0인 지점들 * 활성상태이건 비활성 상태이건 바이러스는 바이러스임의 유의할것 - 비활성화된 지점도 이미 오염된 지점 * BFS 완탐 과정에서 새롭게 오염되는 영역을 카운트 하나씩 카운트
입력사항
* 연구소의 크기 N(4 ≤ N ≤ 50) * 바이러스의 개수 M(1 ≤ M ≤ 10) * 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치
출력사항
* 연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력 * 불가능한 경우 -1
동영상 설명
1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.
package bj.gold.l5;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class BJ_G4_17142_연구소3 {
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokens = null;
static int N;
static int M;
// 바이러스가 있는 지점들(활성 + 비활성)
static List<Point> viruses = null;
// 활성화된 바이러스들
static Point[] activated = null;
static int[][] map;
// 깨끗한 지점들 - 전파의 완료를 파악하기 위한 변수
static int clean;
static int Min;
// 사방 탐색
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static void main(String[] args) throws IOException {
input = new BufferedReader(new StringReader(src));
tokens = new StringTokenizer(input.readLine(), " ");
N = Integer.parseInt(tokens.nextToken());
M = Integer.parseInt(tokens.nextToken());
map = new int[N][N];
activated = new Point[M];
viruses = new LinkedList<>();
for (int r = 0; r < N; r++) {
tokens = new StringTokenizer(input.readLine(), " ");
for (int c = 0; c < N; c++) {
map[r][c] = Integer.parseInt(tokens.nextToken());
if (map[r][c] == 2) {
// 바이러스 지점 저장하기
viruses.add(new Point(r, c, 0));
} else if (map[r][c] == 0) {
// 오염되지 않은 지점 카운트 하기
clean++;
}
}
}
Min = Integer.MAX_VALUE;
// 전체 바이러스 중에서 M개의 활성 바이러스를 고르는 것에서 부터 시작
combi(M, 0);
System.out.println(Min == Integer.MAX_VALUE ? -1 : Min);
}
static void pollution() {
boolean[][] visited = new boolean[N][N];
Queue<Point> q = new LinkedList<>();
// 활성화된 바이러스 들을 기점으로 BFS 탐색
for (int i = 0; i < activated.length; i++) {
q.offer(activated[i]);
visited[activated[i].r][activated[i].c] = true;
}
// 바이러스가 전파되는데 소요되는 시간
int time = 0;
// 오염된 지역의 개수
int polluted = 0;
while (!q.isEmpty()) {
Point front = q.poll();
// 시간은 front의 depth로 변경
time = front.d;
// 해당 지점이 공백이었다면 polluted 증가. 비활성화된 바이러스 구간은 오염되지 않음 중의
if (map[front.r][front.c] == 0) {
polluted++;
}
// 만약 오염지역의 개수가 clean과 동일하면 그만~
if (polluted == clean) {
Min = Math.min(time, Min);
break;
}
for (int d = 0; d < dirs.length; d++) {
int nr = front.r + dirs[d][0];
int nc = front.c + dirs[d][1];
if (isIn(nr, nc) && map[nr][nc] != 1 && !visited[nr][nc]) {
visited[nr][nc] = true;
Point np = new Point(nr, nc, front.d + 1);
q.offer(np);
}
}
}
}
static boolean isIn(int r, int c) {
return 0 <= r && r < N && 0 <= c && c < N;
}
// 그냥 뻔한 조합 코드
static void combi(int ti, int si) {
if (ti == 0) {
pollution();
return;
}
for (int i = si; i < viruses.size(); i++) {
activated[ti - 1] = viruses.get(i);
combi(ti - 1, i + 1);
}
}
static class Point {
int r, c;
int d;
public Point(int r, int c, int d) {
this.r = r;
this.c = c;
this.d = d;
}
@Override
public String toString() {
return "[r=" + r + ", c=" + c + ", d=" + d + "]";
}
}
}