[BOJ] 16998. Baaaaaaaaaduk2 (Easy)

조합과 BFS가 합쳐진 문제이다.

이 문제는 바둑판에서 0이 되는 곳의 위치 2개를 뽑는 조합을 사용한다음, 1로 둘러쌓인 2의 최대 갯수를 구하는 BFS문제이다. 이 문제에 주의할점은 2가 테두리 혹은 1로 만 둘러쌓여야 하는데 이과정에서 나는 flag변수 possible을 하나 선언하여 0이랑 인접해있으면 count를 할수 없게 처리하였다.

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_16988_Baaaaaaaaaduk2Easy {
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static int[][] mapOriginal;
    static int[][] mapTest;
    
    static boolean[] visitComb;
    static boolean[][] visitMap;
    
    static Pos[] pick;
    static List<Pos> list;
    
    static int R,C,answer;
    
    static Queue<Pos> queue;
    
    static class Pos{
        int i, j;
        Pos(int i,int j){
            this.i=i;this.j=j;
        }
    }
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        st=new StringTokenizer(br.readLine());
        R=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        
        mapOriginal=new int[R][C];
        mapTest=new int[R][C];
        list=new ArrayList<>();
        queue = new LinkedList<>();
        
        for(int i=0;i<R;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<C;j++) {
                int num=Integer.parseInt(st.nextToken());
                mapOriginal[i][j]=num;
                mapTest[i][j]=num;
                if(num==0)
                    list.add(new Pos(i, j));
            }
        }
        
        visitComb=new boolean[list.size()];
        pick=new Pos[2];
        
        
        answer=0;
        comb(0,0);
        System.out.println(answer);
        
    }
    
    static void comb(int start,int depth) {
        if(depth==2) {
            for(Pos cur : pick) 
                mapTest[cur.i][cur.j]=1;
            bfs();
            
            for(Pos cur : pick) 
                mapTest[cur.i][cur.j]=0;
            
            return;
        }
        
        for(int i=start;i<list.size();i++) {
            if(visitComb[i]==false) {
                visitComb[i]=true;
                pick[depth]=list.get(i);
                comb(i,depth+1);
                visitComb[i]=false;
            }
        }
        
    }
    
    static void bfs() {
        visitMap=new boolean[R][C];
        int sum=0;
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                if(mapTest[i][j]==2 && visitMap[i][j]==false) {
                    boolean possible=true;
                    visitMap[i][j]=true;
                    queue.offer(new Pos(i, j));
                    int count=0;
                    while(!queue.isEmpty()) {
                        Pos cur=queue.poll();
                        count+=1;
                        
                        for(int dir=0;dir<4;dir++) {
                            int nextI=cur.i+di[dir];
                            int nextJ=cur.j+dj[dir];
                            
                            if(nextI<0 || nextI>=R || nextJ<0 ||nextJ>=C)
                                continue;
                            
                            if(mapTest[nextI][nextJ]==2 && visitMap[nextI][nextJ]==false) {
                                queue.offer(new Pos(nextI, nextJ));
                                visitMap[nextI][nextJ]=true;
                            }
                            
                            if(mapTest[nextI][nextJ]==0) {
                                possible=false;
                            }
                            
                        }
                    }
                    
                    if(possible==true) {
//                        System.out.println(i+","+j+","+count);
                        sum+=count;
                    }
                }
                
                
            }
        }
        answer=Math.max(answer, sum);
    }
    
    
}