연구소3의 풀이에서 몇가지가 수정되었다.
바이러스를 배치하지 않은곳은 사실상 0이라고 생각해야 하는점이 차이점이었다. 그래서
bfs를 돌때 map[i][j]=2 인곳을 0으로 바꿔주며 cnt++를 해주었는데 이렇게 되면 진짜 바이러스를 놓는 곳도 포함이 되버리므로 map[][] = 3을 해줄때 다시 cnt--를 해주었다.
또한 연구소3에서는 zerocnt가 0인경우는 if문을 통해서 바로 0을 출력하게 했지만 이 경우는 바이러스 놓을곳은 4개이지만 실제로 바이러스를 2개만 놓는 경우가 발생하는경우가 있으므로 if문을 제거했다.
import java.util.*;
public class Main {
static int n;
static int m;
static boolean [] viruschk;
static int res = Integer.MAX_VALUE;
static int temper =0;
static boolean minuschk = false;
static int zerocnt = 0;
//상 우 하 좌
static int [] diry = {-1,0,1,0};
static int [] dirx = {0,1,0,-1};
static int [][] originMap; //맵 원본
public static class Node{
int y;
int x;
public Node(int y, int x){
this.y=y;
this.x=x;
}
public String toString(){
return "y : "+y+" x : "+x;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt(); //바이러스를 놓을수 있는 위차
originMap = new int[n][n];
int [][] map = new int[n][n];
List<Node> viruspos = new ArrayList<>();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = sc.nextInt();
originMap[i][j] = map[i][j];
if(map[i][j]==2){
viruspos.add(new Node(i,j));
}else if(map[i][j]==0){
zerocnt++;
}
}
}
Node [] pos = new Node[m];
viruschk = new boolean[viruspos.size()];
//위치 설정
dfs(0,0,viruspos,pos,map);
System.out.println(minuschk ? -1 : res);
}
public static void dfs(int idx,int checker, List<Node>viruspos,Node [] pos, int [][]map){
if(idx==m){
//bfs돌리기
bfs(pos,map);
// -1 이 나온 상태에서 res값이 갱신되지 않았다는것은, 모든 칸에 바이러스를 퍼트리는 경우가 나오지 않았다는 뜻이므로
//minuschk라는 값을 true로 바꿔둬서 마지막에 -1을 사용할지 res값을 사용할지 체크한다.
if(temper == -1){
if(res==Integer.MAX_VALUE){
minuschk = true;
}
}else{
//만약에 res값이 -1이 아닌 값으로 바꼈다면, minuschk를 false로바꿔서 마지막에 res가 -1로 되는 것을 막는다.
res = Math.min(res,temper);
minuschk = false;
}
//temper값 초기화...
temper=0;
return;
}
for(int i=checker; i<viruspos.size(); i++){
if(viruschk[i]){
continue;
}
pos[idx] = viruspos.get(i);
viruschk[i] = true;
dfs(idx+1,i,viruspos,pos,map);
viruschk[i] = false;
}
}
public static void bfs(Node [] pos, int [][]map){
Queue<Node> queue = new LinkedList<>(); //temp 에서 모인 바이러스들을 확신시키는 로직 수
Queue<Node> temp = new LinkedList<>(); //해당 초동안에 확산된 바이러스들을 담음
int cnt = zerocnt;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = originMap[i][j];
if(map[i][j]==2){
map[i][j]=0;
cnt++;
}
}
}
for(int i=0; i<pos.length; i++){
int now_y = pos[i].y;
int now_x = pos[i].x;
map[now_y][now_x]=3; //진짜 바이러스
cnt--;
temp.add(new Node(now_y,now_x));
}
while(!temp.isEmpty()) {
while(!temp.isEmpty()){
queue.add(temp.poll());
}
boolean timer = false; //이번 초동안에 확산시킨 바이러스가 있다면 ++를 해준다.
while (!queue.isEmpty()) {
Node now = queue.poll();
for (int i = 0; i < 4; i++) {
int now_y = now.y + diry[i];
int now_x = now.x + dirx[i];
if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < n) {
if (map[now_y][now_x] == 0) {
cnt--;
map[now_y][now_x] = 3;
timer = true;
temp.add(new Node(now_y, now_x));
}
}
}
}//queue.isEmpty()
if(timer){
temper++;
}
if(cnt==0){
break;
}
}//temp.isEmpty()
//체크
temper = cnt !=0 ? -1 : temper;
}
}