[JAVA][백준 2234][BFS][비트마스킹] 성곽 - 컴도리돌이

---

 

문제에 대한 대략적인 설명은 

다음 링크에 적어놨습니다.

ㅎㅎㅎ

 

[Python][백준 2234][BFS] 성곽 - 컴도리돌이

 

해당 링크는 파이썬으로 풀어서

혹시 이해가 안되시는 분을 위해

주석을 달아놨습니다.

🥲

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n,m;
    static int [][] arr;
    static int [][] visited;
    // 순서대로 서북동남
    static int [] dx = {0,-1,0,1};
    static int [] dy = {-1,0,1,0};
    // 서북동남 인덱스와 비트마스킹하기 위한 배열 
    static int [] bitMasking = {1,2,4,8};
    // 방의 개수
    static int roomNum = 0; 
    // 가장 큰 방을 가진 수
    static int maxRoom = -1;
    // 방의 번호와 방의 크기 맵핑
    static HashMap<Integer,Integer> roomNumAndSize = new HashMap<>(); 
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m][n];
        visited = new int[m][n];
        for(int i=0; i< m ; i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0; j< n ; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // (i,j)를 방문하지 않으면 BFS 탐색
        // 탐색할 수 있는 모든 좌표를 roomNum을 할당해준다.
        // 탐색 후에 roomNum을 증가 시킨다.
        for(int i=0; i <m ; i++){
            for(int j=0; j<n ; j++){
                if(visited[i][j] == 0) {
                    bfs(i,j,roomNum+1);
                    roomNum+=1;
                }
            }
        }
        
        // 인정한 서로 다른 두 방의 합을 구하기
        int ans = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n ; j++) {
                // 현재 (i,j) 와 서북동남으로 인접한 (ni,nj)와 방번호 비교
                // 방번호가 같을 경우 continue
                // 방번호가 다를 경우 맵핑한 함수로 현재 방번호 크기와 인접한 방번호 크기의 합을 ans와 비교
                // max값을 ans에 저장
                for(int k=0; k<4; k++) {
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    if(ni < 0 || ni >= m || nj < 0 || nj >=n) continue;
                    if(visited[ni][nj] == visited[i][j]) continue;
                    int a = visited[ni][nj];
                    int b = visited[i][j];
                    ans = Math.max(ans,roomNumAndSize.get(a) + roomNumAndSize.get(b));
                }
            }
        }

        // 문제에서 요구한 방의 개수, 가장 큰 방의 개수, 인접한 방의 합중 max값 출력
        System.out.println(roomNum);
        System.out.println(maxRoom);
        System.out.println(ans);
    }

    public static void bfs(int x,int y,int flag){

        Deque<int []> dq = new LinkedList<>();
        dq.add(new int[] {x,y});
        visited[x][y] = flag;
        int roomCnt = 0;
        while(!dq.isEmpty()){
            int cx,cy;
            int[] pos = dq.poll();
            cx = pos[0];
            cy = pos[1];
            // 방의 개수 증가 시킨다.
            roomCnt +=1 ;

            for(int i=0; i<4 ; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if(visited[nx][ny] != 0 ) continue;
                // 현재 arr 값과 bitMaking i번째 값과 and 연산을 해서
                // 공통된게 없으면 q에 다음 좌표를 넣어준다.
                // 다음 (nx,ny)좌표를 방번호로 방문표시
                if((arr[cx][cy] & bitMasking[i]) == 0) {
                    visited[nx][ny] = flag;
                    dq.add(new int[] {nx,ny});
                }
            }
        }
        // 가장 큰 방 크기 업데이트
        maxRoom = Math.max(maxRoom,roomCnt);
        // 방 번호 - 방 크기 맵핑
        roomNumAndSize.put(flag,roomCnt);
    }

}

 

---