[25.03.20] 연구소

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

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

// The main method must be in a class named "Main".
class Main {
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static int[][] score;
    static int N;
    static int M;
    static int maxSafetyZone = Integer.MIN_VALUE;
    static Queue<int[]> q; 
    static ArrayList<int[]> virusList;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        N = Integer.parseInt(s[0]);
        M = Integer.parseInt(s[1]);
        score=new int[N][M];
        virusList = new ArrayList<int[]>();
        
        for(int i=0; i<N; i++){
            s = br.readLine().split(" ");
            for(int j=0; j<M; j++){
                int temp = Integer.parseInt(s[j]);
                if(temp==2){
                    int[] virus = new int[] {i,j};
                    virusList.add(virus);
                }
                score[i][j]= temp;
            }
        }

        dfs(0);
        System.out.printf("%d",maxSafetyZone);
        
    }

    static void dfs(int depth){
        if(depth==3){
            bfs();
            return;
        }
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(score[i][j]==0){
                    score[i][j]=1;
                    dfs(depth+1);
                    score[i][j]=0;
                }
            }
        }
    }

    static void bfs(){
        int[][] copyScore = new int[N][M];
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                copyScore[i][j] = score[i][j];
            }
        }
        for(int[] virus : virusList){
            q=new LinkedList<int[]>();
            q.add(virus);
            while(!q.isEmpty()){
                int[] nowVirus = q.poll();
                for(int i=0; i<4; i++){
                    int nextX = nowVirus[0]+dx[i];
                    int nextY = nowVirus[1] +dy[i];
                    if(nextX>=0 && nextX<N && nextY>=0 && nextY<M){
                        if(copyScore[nextX][nextY]==0){
                            copyScore[nextX][nextY]=2;
                            int[] nextVirus = new int[] {nextX,nextY};
                            q.add(nextVirus);
                        }
                    }
                }
            }
        }
        int count = countSafety(copyScore);
        maxSafetyZone = Math.max(count, maxSafetyZone);
    }
    static int countSafety(int[][] arr){
        int count =0;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(arr[i][j]==0){
                    count++;
                }
            }
        }
        return count;
    }
    
}