#백준_2234 성곽 - Java 자바

# 유형 : BFS + 비트 마스크

# 난이도 : 골드 4

# BFS + 비트 마스크 알고리즘을 사용하여 접근한 문제. 맨 처음에는 비트 마스크 안 쓰고 하려 했는데, 코드가 너무 길어지는 것 같아서 비트 마스크를 사용하였다. 

*** 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8 *** 

예를 들어 15가 주어지면 1,2,4,8로 비트 체킹을 하면 다 1,2,4,8을 출력한다. 이 경우에는 4가지 방향 모두 벽이 있다는 뜻이다. 13의 경우에는 1,0,4,8을 출력하므로 북쪽에는 벽이 없다는 말이다. 따라서 비트 마스크를 사용하여 다음 방향으로 이동할 수 있는지를 체크하며 BFS를 진행하면 된다. BFS를 호출한 횟수가 방의 개수이고, 벽을 제거했을 때도 똑같이 비트마스크를 사용하며 벽을 허물고 BFS 돌리면서 해결하면 된다.

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2234 {
    static int R,C;
    static int arr[][];
    static boolean visit[][];
    static int moveX[] = {-1,0,1,0};
    static int moveY[] = {0,-1,0,1};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        
        arr = new int[R][C];
        visit = new boolean[R][C];
        for(int r=0; r<R; r++) {
            st = new StringTokenizer(br.readLine());
            for(int c=0; c<C; c++) {
                arr[r][c] = Integer.parseInt(st.nextToken());
            }
        }
        
        int room = 0;
        int max = 0;
        for(int r=0; r<R; r++) {
            for(int c=0; c<C; c++) {
                if(!visit[r][c]) {
                    max = Math.max(max, bfs(r,c));
                    room++;
                }
            }
        }
        System.out.println(room);
        System.out.println(max);
 
        for(int r=0; r<R; r++) {
            for(int c=0; c<C; c++) {
                for(int bit=1; bit<=8; bit<<=1) {
                    if((arr[r][c] & bit)!=0) {
                        visit = new boolean[R][C];
                        arr[r][c] -= bit;
                        max = Math.max(max, bfs(r,c)); 
                        arr[r][c] += bit;
                    }
                }
            }
        }
//        이 성에 있는 방의 개수
//        가장 넓은 방의 넓이
//        하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
        System.out.println(max);
    }
    private static int bfs(int row, int col) {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(col, row));
        visit[row][col] = true;
        int count = 1;
        while(!queue.isEmpty()) {
            
            Point po = queue.poll();
            int bit = 1;
//            System.out.println(po);
            for(int d=0; d<4; d++) {
                if((arr[po.y][po.x] & bit)==0) {
                    int newX = po.x + moveX[d];
                    int newY = po.y + moveY[d];
                    if (!(0 <= newY && newY < R && 0 <= newX && newX < C))
                         continue;
                    if(0<=newY && newY<R && 0<=newX && newX<C && !visit[newY][newX]) {
                        count++;
                        visit[newY][newX]=true;
                        queue.add(new Point(newX, newY));
                    }
                }
                bit<<=1;
            }
        }
        return count;
    }
    
    
}