[백준 BOJ] 17142. 연구소 3

import java.util.*;
public class Main {
	static int[][] a;
	static int[] vx = new int[11];
	static int[] vy = new int[11];
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static boolean[][] chk;
	static int n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int m = sc.nextInt();
		a = new int[n][n];
		chk = new boolean[n][n];
		int vIdx = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				a[i][j] = sc.nextInt();
				if(a[i][j] == 2) {
          /* vx, vy에 초기 바이러스 위치를 저장한다.
          	 결과적으로 vIdx는 바이러스의 개수를 의미하게 된다.*/
					vx[vIdx] = i;
					vy[vIdx++] = j;
				}
			}
		}
    /* min은 모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 담는 변수 */
		int min = 3000;
		Queue<Pnt> q = new LinkedList<Pnt>();
    /* 비트마스킹 방식을 사용하여 전체 바이러스의 개수 중에서 활성 상태로 만들 m개를 선택한다. */
		for(int i=0; i<(1<<vIdx); i++) {
			int cnt = 0;
			for(int j=0; j<vIdx; j++)
				if((i & (1<<j)) != 0) cnt++;
			
			if(cnt != m) continue;
      /* 바이러스의 방문 여부를 확인하기 위한 chk 배열 */
			for(int k=0; k<n; k++)
				for(int l=0; l<n; l++)
					chk[k][l] = false;
			/* 활성화 시킬 바이러스의 위치를 queue에 넣어준다. */
			for(int j=0; j<vIdx; j++) {
				if((i & (1<<j)) != 0) {
					q.add(new Pnt(vx[j],vy[j]));
					chk[vx[j]][vy[j]] = true;
				}
			}
			int time = 0;
			while(!q.isEmpty()) {
        /* check 함수는 모든 빈칸에 바이러스가 퍼졌을 때 true를 반환한다. */
				if(check()) {
					if(time < min) min = time;
					break;
				}
				time++;
				int qs = q.size();
				while(qs-- > 0) {
					Pnt p = q.poll();
					for(int k=0; k<4; k++) {
						int ni = p.i + dx[k];
						int nj = p.j + dy[k];
						if(ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            /* 칸이 벽이거나 이미 방문한 적이 있으면 queue에 넣지 않고 넘어간다. */
						if(a[ni][nj] == 1 || chk[ni][nj]) continue;
						chk[ni][nj] = true;
						q.add(new Pnt(ni,nj));
					}
				}
			}
			q.clear();
		}
    /* min이 갱신되지 않은 경우에는 모든 빈칸에 바이러스를 퍼뜨리는 방법이 없다는 것을 의미한다. */
		if(min == 3000) min = -1;
		System.out.println(min);
	}
  /* 각 칸의 좌표를 담는 Pnt class */
	static class Pnt{
		int i, j;
		public Pnt(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}
  /* 모든 빈칸에 바이러스가 퍼졌을 때 true를 반환하는 check 함수이다. */
	static boolean check() {
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(a[i][j] == 1 || a[i][j] == 2 || chk[i][j]) continue;
				return false;
			}
		}
		return true;
	}
}