문제 링크
문제
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.
M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.
시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.
연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.
입력
첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.
둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.
출력
연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.
알고리즘: BFS, 브루트포스
풀이
연구소 2와 유사한 문제이다. 풀이는 똑같다. 바이스러가 위치한 좌표 중에 활성화 시킬 M개의 바이러스를 고르는 모든 경우의 수(브루트포스)를 구하면 된다. 조합을 사용해서 각 조합마다 BFS를 돌리고 그 중 최소 시간을 출력하면 된다.
근데 여기서 주의할 점은 2는 바이스러를 놓을 수 있는 빈칸의 위치가 아니고, 바이스러의 위치라는 점을 인지해야 한다. 그렇기 때문에 빈칸을 의미하는 0의 좌표만 바이러스가 퍼졌는지 체크해야 한다. 모든 0의 좌표의 바이러스가 방문했다면, 더 이상 탐색을 진행하지 않고 min값이 갱신될 수 있는지 확인하면 된다.
소스 코드
import java.io.*;
import java.util.*;
class Point {
int x,y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static final int dx[] = {-1, 0, 1, 0};
static final int dy[] = {0, -1, 0, 1};
static int N,M;
static int lab[][];
static boolean visited[][];
static ArrayList<Point> bi_list = new ArrayList<>();
static int blank_length = 0;
static ArrayList<Integer> result = new ArrayList<>();
static int min = Integer.MAX_VALUE;
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());
lab = new int[N][N];
for(int i=0; i<N; i++) {
StringTokenizer n_st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
lab[i][j] = Integer.parseInt(n_st.nextToken());
if(lab[i][j] != 1) {
if(lab[i][j] == 2) bi_list.add(new Point(j,i));
else if(lab[i][j] == 0) blank_length += 1;
}
}
}
combination(0);
if(min == Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(min);
}
static void BFS(ArrayList<Integer> b) {
Queue<Point> que = new LinkedList<>();
for(int i=0; i<b.size(); i++) {
Point sp = bi_list.get(b.get(i));
que.add(sp);
visited[sp.y][sp.x] = true;
}
int time = 0;
int bl_cout = 0; // 감염된 칸
while(que.size()!=0) {
if(bl_cout == blank_length) {
min = Math.min(min, time);
return;
}
int sz = que.size();
for(int i=0; i<sz; i++) {
Point n = que.poll();
for(int j=0; j<4; j++) {
int nx = n.x + dx[j];
int ny = n.y + dy[j];
if((nx>=0 && nx<=N-1) && (ny>=0 && ny<=N-1)) {
if(!visited[ny][nx] && lab[ny][nx] != 1) {
que.add(new Point(nx, ny));
visited[ny][nx] = true;
if(lab[ny][nx] == 0) bl_cout += 1;
}
}
}
}
time += 1;
}
}
static void combination(int ind) {
if(result.size()==M) {
visited = new boolean[N][N];
BFS(result);
}
for(int i=ind; i<bi_list.size(); i++) {
result.add(i);
combination(i+1);
result.remove(result.size()-1);
}
}
}