[완탐/BFS]백준_연구소

문제의 키 포인트는 아래와 같다.

1. 벽을 어떻게 세울 것인가?

2. 바이러스를 어떻게 퍼뜨릴 것인가?

 

1을 해결하기 위해서는 완전 탐색을 이용해주었다. 재귀 함수를 이용해 벽을 설치/제거해 주었다.

2를 해결하기 위해서는 BFS를 사용해주었다.

 

어려운 문제는 아니었던 것 같다. 

 

 

import java.awt.Point;
import java.util.*;
 
public class Main {
    
    static int []dx = {-1,1,0,0}; //네방향
    static int []dy = {0,0,1,-1};
    static int[][]Map ;
    static int M;
    static int N;
    static int ans=-1;
    
    public static boolean InRange(int x,int y) {
        if(x >= 0 && x < M && y >=0 && y < N) return true;
        else return false;
    }
    
    public static void BFS() {
        //spread birus.
        Queue<Point> queue = new LinkedList<>();
        int [][]SpreadMap =new int[M][N];
        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) SpreadMap[i][j]=Map[i][j];
        }
        
        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                
                if(SpreadMap[i][j]==2) {
                    queue.add(new Point(i,j));
                    
                    while(!queue.isEmpty()) {
                        Point pt = queue.poll();
                        
                        for(int m=0;m<4;m++) {
                            int nx = pt.x + dx[m];
                            int ny = pt.y + dy[m];
                            
                            if(InRange(nx,ny)==false) continue;
                            if(SpreadMap[nx][ny]==0) {
                                SpreadMap[nx][ny]=2;
                                queue.add(new Point(nx,ny));
                            }
                        }
                    }
                }
                
                
            }
        }//end 2 for
        
        int count = 0;
        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) if(SpreadMap[i][j]==0) count ++ ;
        }
        
        ans = Math.max(ans,count);
    }
    
    public static void BuildBlock(int len) {
        if(len==3) { //return 조건
            //execute BFS 
            BFS();
            return;
        }
        
        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                if(Map[i][j] == 0) {
                    Map[i][j]=1; //설치 
                    BuildBlock(len+1); //재귀 완전탐색
                    Map[i][j]=0; //제거
                }
            }
        }
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();
        Map = new int[M][N];
        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                Map[i][j]=sc.nextInt();
            }
        }
        
        BuildBlock(0);
        System.out.println(ans);
        
    }
}