[BOJ] 17142. 연구소 3

이문제는 조합을 이용하여 선택을 한다음 BFS를 사용하는 문제이다.

조합을 사용하여 바이러스의 위치를 뽑아주고, 그 다음 map에서 그위치를 활성화 시켜준 다음 BFS를 돌았다. 그 후 다시 map을 비활성화 시켜주는 작업을 하였다. 이 문제에서 현재 빈칸이 있는지 check를 할 때 맨처음에는 전체를 다보는 식으로 하였는데 시간초과의 결과를 얻었었다. 그래서 맨처음 입력받을때 빈칸의 갯수를 세어놓고 BFS를 돈다음 그 BFS를 도는 칸이 전체 빈칸의 갯수랑 같다면 true라고 생각해주고 답을 찾아주었다.

package boj2;
 
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_bj_17142_연구소3 {
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static int N;
    static int R;
    
    static int[][] map;
    static boolean[][] visit;
    static Queue<Pos> queue;
    
    static boolean[] visitForComb;
    static Pos[] picks;
    static List<Pos> virus;
    static int V;
    
    static int answer;
    static int countZero;
    
    static class Pos{
        int i,j,time;
        Pos(int i,int j,int t){
            this.i=i;this.j=j;time=t;
        }
    }
    
    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());
        R=Integer.parseInt(st.nextToken());
        
        map=new int[N][N];
        virus=new ArrayList<>();
        countZero=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]==2) {
                    virus.add(new Pos(i, j, 0));
                }else if(map[i][j]==0) {
                    countZero+=1;
                }
            }
        }
        
        picks=new Pos[R];
        V=virus.size();
        visitForComb=new boolean[V];
        
        queue=new LinkedList<>();
        answer=Integer.MAX_VALUE;
        comb(0,0);
        
        if(answer==Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(answer);
    }
    
    static void comb(int start,int depth) {
        if(depth==R) {
            bfs();
            return;
        }
        
        for(int i=start;i<V;i++) {
            if(visitForComb[i]==false) {
                visitForComb[i]=true;
                picks[depth]=virus.get(i);
                comb(i,depth+1);
                visitForComb[i]=false;
            }
        }
        
    }
    
    static void bfs() {
        int time=0;
        visit=new boolean[N][N];
        int count=0;
        for(Pos v : picks) {
            queue.offer(new Pos(v.i, v.j, 0));
            map[v.i][v.j]=-1;
        }
        
        while(!queue.isEmpty()) {
            Pos cur = queue.poll();
            if(map[cur.i][cur.j]==0) {    //빈칸일때만 체크
                count+=1;
                time=Math.max(time,cur.time);
            }
            
            for(int dir=0;dir<4;dir++) {
                int nextI=cur.i+di[dir];
                int nextJ=cur.j+dj[dir];
                
                if(nextI<0 || nextI>=N || nextJ<0 || nextJ>=N)
                    continue;
                
                if((map[nextI][nextJ]==0 || map[nextI][nextJ]==2) && visit[nextI][nextJ]==false) {
                    queue.offer(new Pos(nextI, nextJ, cur.time+1));
                    visit[nextI][nextJ]=true;
                }
            }
        }
        
        for(Pos v : picks) {
            map[v.i][v.j]=2;
        }
        
        if(countZero==count)
            answer=Math.min(answer, time);
    }
    
}