[BOJ] 백준 17141 연구소 2

[문제]

https://www.acmicpc.net/problem/17141

 

 

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int n,m,result = Integer.MAX_VALUE;
	static List<int[]> candidates;
	static boolean[] select;
	static int[][] map,copyM;
	static boolean[][] visit;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	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());
		map = new int[n][n];
		candidates = new ArrayList<>();
		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) {
					candidates.add(new int[] {i,j});
				}
			}
		}
		select = new boolean[candidates.size()];
		combi(0,0);
		System.out.println(result==Integer.MAX_VALUE?-1:result);
	}
	private static void combi(int idx,int cnt) {
		if(cnt==m) {
			spread();
			return;
		}
		for(int i=idx;i<candidates.size();i++) {
			select[i] = true;
			combi(i+1,cnt+1);
			select[i] = false;
		}
	}
	private static void spread() {
		copyM = new int[n][n];
		for(int i=0;i<n;i++) {
			copyM[i] = map[i].clone();
		}
		Queue<int[]> q = new LinkedList<>();
		for(int i=0;i<candidates.size();i++) {
			if(select[i]) { 
				q.offer(new int[] {candidates.get(i)[0],candidates.get(i)[1]});
			}
			else {
				copyM[candidates.get(i)[0]][candidates.get(i)[1]] = 0;
			}
		}
		int time = 0;
		while(!q.isEmpty()) {
			int size = q.size();
			boolean check = false;
			for(int i=0;i<size;i++) {
				int[] curr = q.poll();
				for(int d=0;d<4;d++) {
					int nr = curr[0] + dr[d];
					int nc = curr[1] + dc[d];
					if(nr<0 || nr>=n || nc<0 || nc>=n || copyM[nr][nc]==2 || copyM[nr][nc]==1) continue;
					if(copyM[nr][nc]==0) {
						copyM[nr][nc] = 2;
						check = true;
					}
					q.offer(new int[] {nr,nc});
				}
			}
			if(!check) break;
			time++;
		}
		if(possible()) {
			result = Math.min(result, time);
		}
	}
	private static boolean possible() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(copyM[i][j]==0)
					return false;
			}
		}
		return true;
	}
}