백준 14502 연구소 (자바)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

import java.util.StringTokenizer;

public class algo_14502_김어진 {
	static int N;
	static int M;
	static int answer = 0;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st= new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int[][] board= new int[N][M];
		for (int i = 0; i < N; i++) {
			board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		}
		
		dfs(board,-1,-1,0);
		System.out.println(answer);
	}

	private static void dfs(int[][] board, int row, int col,int cnt) {
		if(cnt==3) {
			int[][] tmpBoard = new int[N][M];
			for (int i = 0; i < N; i++) {
				tmpBoard[i] = Arrays.copyOfRange(board[i], 0, M);
			}
			infect(tmpBoard);
			int blank = safeArea(tmpBoard);
			answer = Math.max(answer, blank);
			return;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if((i>row && board[i][j]==0) ||(i==row&& j>col && board[i][j]==0)) {
					board[i][j]=1;
					dfs(board,i,j,cnt+1);
					board[i][j]=0;
				}
			}
		}
		
	}

	private static int safeArea(int[][] board) {
		int blank=0;
	
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(board[i][j]==0) {
					blank++;
				}
			}
		}
		return blank;
	}

	private static void infect(int[][] board) {
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(board[i][j]==2) {
					bfs(board,i,j);
				}
			}
		}
		
	}

	private static void bfs(int[][] board, int x, int y) {
		
		boolean[][] check = new boolean[N][M];
		Queue<Integer[]> q=new LinkedList<Integer[]>();
		q.add(new Integer[] {x,y});
		check[x][y]=true;
		
		while(!q.isEmpty()) {
			Integer[] pos = q.poll();
			x = pos[0];
			y =pos[1];
			for (int i = 0; i < 4; i++) {
				int nx = x+dx[i];
				int ny = y + dy[i];
				if(nx>=0 && nx < N && ny>=0 && ny<M &&board[nx][ny]==0)
				{
					q.add(new Integer[] {nx,ny});
					board[nx][ny]=2;
					check[nx][ny]=true;
					
				}
			}
		}
		
		
	}

}