[백준] 14502 : 연구소 - JAVA(자바) - 사좋배 공유

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

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int N;
	static int M;
	static int[][]arr;
	static int[][]temp;
	static ArrayList<Integer> list;
	static int maxnum;
	static int[]dx= {-1,0,1,0};
	static int[]dy= {0,1,0,-1};
	static boolean[][] visited;
	static int[][]temparr;
	static int MAX;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		arr=new int[N][M];
		temp=new int[N][M];
		list= new ArrayList<Integer>();
		MAX = Integer.MIN_VALUE;
		int cnt=1;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				arr[i][j]=sc.nextInt();
				temp[i][j]=cnt++;
			}
		}
		maxnum=cnt;
		dfs(1);
		System.out.println(MAX);
	}
	private static void dfs(int index) {
		if(list.size()==3) {
			//temparr 초기화과정
			temparr= new int[N][M];
			visited=new boolean[N][M];
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					temparr[i][j]=arr[i][j];
				}
			}
			
			
			//조합으로 뽑기
			int cnt=0;
			loop: for(int i=0;i<3;i++) {
				int number= list.get(i);
				for(int j=0;j<N;j++) {
					lo:for(int k=0;k<M;k++) {
						if(number==temp[j][k]&&arr[j][k]==0) {
							temparr[j][k]=1;
							break lo;
						}else if(number==temp[j][k]&&arr[j][k]!=0){
							cnt++;
							break loop;
						}
					}
				}
			}
			//3개다 0으로 빈곳이면
			if(cnt==0) {
				for(int i=0;i<N;i++) {
					for(int j=0;j<M;j++) {
						if(temparr[i][j]==2) {
							//바이러스를 표시한다.
							visited[i][j]=true;
							dfs2(i,j);
						}
					}
				}
				int result=0;
				for(int i=0;i<N;i++) {
					for(int j=0;j<M;j++) {
						if(temparr[i][j]==0) {
							result++;
						}
					}
				}
				if(MAX<result) {
					MAX=result;
				}
			}
			return;
		}
		
		//3개뽑기
		for(int i=index;i<maxnum;i++) {
			list.add(i);
			dfs(i+1);
			list.remove(list.size()-1);
		}
	}
	
	private static void dfs2(int x,int y) {
		for(int i=0;i<4;i++) {
			int rx= x+dx[i];
			int ry=y+dy[i];
			if(rx<0||ry<0||rx>=N||ry>=M) {
				continue;
			}
			if(visited[rx][ry]==false&&temparr[rx][ry]==0) {
				visited[rx][ry]=true;
				temparr[rx][ry]=2;
				dfs2(rx,ry);
			}
		}
	}
}