[BFS,비트마스킹] - G3_2234_성곽

https://www.acmicpc.net/problem/2234

2234번: 성곽

🌿 - 문제 설명

 

📌- 풀이

다양한 풀이 방법이 있겠지만 여기서는 일단 BFS, 비트마스킹을 사용해서 풀었고 

Room 객체 배열을 만들어서 각자 배열에 부모의 번호, 방의 크기, 초기값에 대한 정보를 담았다.

 

0,0부터 BFS를 돌면서 부모가 누구인지 각각의 배열에 담으면서 -> 1과 2번을 구했고

 

 

이런식으로 부모의 위치에 해당 방의 크기값이 저장 된다.

 

 

 

다시 한번 반복문을 돌면서 해당하는 배열의 벽을 하나씩 제거 했을 때 최고값을 갱신하면서 -> 3의 답을 구했다.

 

대략적인 설명은 코드와 함께 주석으로 적어 놓았다.

 

더 쉬운 방법이 분명 많을거라 생각한다. 

 

BFS문제여서 빠르게 풀 수 있을 줄 알았는데, 비트마스킹을 잘 숙지하고 있지 않아서 약 1시간 반정도 걸린 것 같다.

더 집중하고 많이 풀어보면서 시간 단축하도록 하자.

 

 

🔥 - Java 전체 코드

package BFS.G3_2234_성곽;

import java.io.*;
import java.util.*;

public class Main {
        static int N,M,roomCount=0,roomMax=0,max=0;
        static Room[][] arr;

        static int[] dx = {0,-1,0,1}; // 1,2,4,8 기준
        static int[] dy = {-1,0,1,0}; // 서,북,동,남



    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new Room[M][N];

        for(int i=0;i<M;i++){  // 초기 값 셋팅
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                int n = Integer.parseInt(st.nextToken());
                arr[i][j] = new Room(0,n,0); // 초기 부모는 0 , n은 입력값, 사이즈는 아직 모르기때문에 0

            }
        }

        for(int i =0;i<M;i++){ // bfs를 돌면서 부모와 방의 넓이, 방 갯수를 체크함
            for(int j=0;j<N;j++){
                if(arr[i][j].parent == 0){
                    bfs(i,j);
                    roomCount++;
                }
            }
        }


        for(int i=0;i<M;i++){ // 전체 방문하면서 각자의 위치에서 벽을 허물었을 때 가장 큰 값 찾기
            for(int j=0;j<N;j++){
                calRoom(i,j);
            }
        }

        System.out.println(roomCount);
        System.out.println(roomMax);
        System.out.println(max);

    }

    public static void bfs(int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x,y});
        arr[x][y].parent = x*N + (y+1); // 부모의 방번호
        int size =0;
        while(!queue.isEmpty()){
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];
            size++;
            for(int i=0;i<4;i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                // if 조건 - 부모가 0이라면 방문한 곳이 아니기 때문에 방문 해야하고 && 현재 방의 위치에서 벽이 없는 쪽이라면 방문해야 하기 때문에 체크
                if(nx >=0 && nx<M && ny>=0 && ny<N && arr[nx][ny].parent == 0 && (arr[cx][cy].number & (int)Math.pow(2,i)) == 0 ){
                    queue.add(new int[]{nx,ny});
                    arr[nx][ny].parent = x*N + (y+1);
                }
            }

        }
        arr[x][y].roomSize = size;
        roomMax = Math.max(size,roomMax);

    }

    public static void calRoom(int x, int y){
       
        Room room = arr[x][y];
        for(int i =0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 벽이 있고, 벽 너머의 부모가 다르다면 넓이 더하기
            if((room.number & (int)Math.pow(2,i)) !=0  && nx>=0 && nx<M && ny>=0 && ny<N && room.parent != arr[nx][ny].parent){
                int px = (room.parent-1)/N;
                int py = (room.parent-1)%N;
                int nxP = (arr[nx][ny].parent-1)/N;
                int nyP = (arr[nx][ny].parent-1)%N;
                max = Math.max(max, arr[px][py].roomSize + arr[nxP][nyP].roomSize);
            }

        }

    }

}

class Room{ 
        int parent; // 같은 공간에 있다면 부모의 위치만 알아도 크기를 알 수 있기 때문에 이렇게 만듬
        int number; // 초기에 입력받는 값 저장
        int roomSize; // 자기가 속한 방의 사이즈를 알기 위함 - 부모만 값을 가지고 나머지는 부모를 참조하도록 만듬 
        Room(int x, int number,int size) {
            this.parent = x;
            this.number = number;
            this.roomSize = size;
        }
}