14502 연구소

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Baekjoon14502 {
    static final int dx[] = {0,0,1,-1};  //상하좌우 방향 설정
    static final int dy[] = {1,-1,0,0};  //상화좌우 방향 설정
    static int map[][];
    static int copyMap[][];
    static int n,m;
    static int maxSafeZone = Integer.MIN_VALUE; //최대값을 찾기 위한 최소값 설정
    static class Virus {
        int x;
        int y;
        Virus(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    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][m];
        for(int i=0; i<n;i++){
            st = new StringTokenizer(br.readLine());
            int j=0;
            while(st.hasMoreTokens()){
                map[i][j]=Integer.parseInt(st.nextToken());
                j++;
            }
        }
        
        buildWall(0);
        System.out.println(maxSafeZone);
        
    }
    static void buildWall(int wallCount){
        if(wallCount==3){
         SpeadVirus();
            return;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(map[i][j]==0){
                    map[i][j]=1;
                    buildWall(wallCount+1);
                    map[i][j]=0;
                }
            }
        }
    }
    static void SpeadVirus(){
        copyMap = new int[n][m];
        for(int i=0;i<n;i++){
            copyMap[i] = map[i].clone();
        }
        Queue<Virus> q = new LinkedList<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(copyMap[i][j]==2){
                    q.add(new Virus(i, j));
                }
            }
        }
        while(!q.isEmpty()){
            Virus virus = q.poll();
            for(int k=0;k<4;k++){
                int x = virus.x + dx[k];
                int y = virus.y + dy[k];
                if(x>=0 && x<n && y>=0 && y< m){
                    if(copyMap[x][y]==0){
                        copyMap[x][y]=2;
                        q.add(new Virus(x,y));
                    }
                }
            }
        }
        safeZoneNumber(copyMap);
    }
    static void safeZoneNumber(int[][] copyMap){
        int count=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(copyMap[i][j]==0) count++;
            }
        }
        if (maxSafeZone<count){
            maxSafeZone=count;
        }
    }    
}

DFS로 풀이를 하니깐 별로인거같아서.. 다시 풀 예정 .. 지인분이 조합을 사용해보라해서 조합공부후 다시 풀것이다.