[BOJ] 14502. 연구소

구현할 것이 상당히 많은 문제였다.

기본적으로 벽이 갈수 있는 위치 3군대를 찾는 과정을 거치고 벽을 셋팅후 BFS하여 모든 0의 갯수를 세어주는 과정을 찾는 문제였다. 조합과 BFS를 연속하여 구현하기 때문에 빼먹을수 있는 부분이 많은 문제이므로 꼼꼼하게 함수로 나누어 코딩하는게 중요한 문제였다.

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_14502_연구소 {
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static int[][] originalMap;
    static boolean[][] visitForBFS;
    static int[][] map;
    static int R,C;
    
    static Pos[] result;
    static boolean[] visitForComb;
    
    static Queue<Pos> queue;
    static List<Pos> list;
    
    static class Pos{
        int i,j;
        Pos(int i,int j){
            this.i=i;this.j=j;
        }
    }
    
    static int answer;
    
    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());
        
        list=new ArrayList<>();
        originalMap=new int[R][C];
        map=new int[R][C];
        
        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());
                originalMap[i][j]=num;
                if(num==0)
                    list.add(new Pos(i, j));
            }
        }
        
        visitForComb=new boolean[list.size()];
        result=new Pos[3];
        
        queue=new LinkedList<>();
        answer=0;
        comb(0,0);
        System.out.println(answer);
    }
    
    static void comb(int start,int depth) {
        if(depth==3) {
            check();
            
            int temp=0;
            for(int i=0;i<R;i++) {
                for(int j=0;j<C;j++) {
                    if(map[i][j]==0)
                        temp+=1;
                }
            }
            answer=Math.max(answer, temp);
            return;
        }
        
        for(int i=start;i<list.size();i++) {
            if(visitForComb[i]==false) {
                visitForComb[i]=true;
                result[depth]=list.get(i);
                comb(i,depth+1);
                visitForComb[i]=false;
            }
        }
    }
    
    static void check() {
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                map[i][j]=originalMap[i][j];
            }
        }
        for(int index=0;index<3;index++) {
            map[result[index].i][result[index].j]=1;
        }
        
        
        bfs();
    }
    
    static void bfs() {
        visitForBFS=new boolean[R][C];
        
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                if(map[i][j]==2 && visitForBFS[i][j]==false) {
                    queue.add(new Pos(i, j));
                    visitForBFS[i][j]=true;
                    
                    while(!queue.isEmpty()) {
                        Pos cur=queue.poll();
                        
                        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(map[nextI][nextJ]==0 && visitForBFS[nextI][nextJ]==false) {
                                queue.offer(new Pos(nextI, nextJ));
                                visitForBFS[nextI][nextJ]=true;
                                map[nextI][nextJ]=2;
                            }
                        }
                    }
                }
            }
        }
    }
}