[백준] 2234 성곽- 비트마스킹(BitMasking) + BFS(너비우선탐색) JAVA

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

2234번: 성곽

코드설명

비트마스킹과 BFS 문제입니다.

 

문제에서 벽이 주어지는

서쪽 : 1 -> 1 (2진수)

북쪽 : 2 -> 10 (2진수)

동쪽 : 4 -> 100 (2진수)

남쪽 : 8 -> 1000 (2진수)

 

위와 같이 주어집니다.

이떄 만약 11이 주어진다고 가정해보겠습니다.  11은 1 + 2 + 8 로, 즉, 서쪽벽, 북쪽벽, 남쪽벽으로 이루어져있다고 할 수 있습니다. 문제의 예시로 보면, map[0][0] 을 의미합니다. 해당 문제에 존재하는 그림을 참고하시기 바랍니다.

7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

 

비트마스킹을 활용하여 서쪽, 북쪽, 동쪽, 남쪽 4가지 방향이 포함되었는지 확인하기 위해 & 연산자를 활용하여 값이 0 보다 크다면 해당 벽으로 이루어진 숫자이므로 벽이 존재하는것으로 판단합니다.

if( (map[temp.r][temp.c] & (1 << dir) ) == 0) { //만약 해당방향에 벽이 없다면, 이동시킨다. 만약 벽이 존재한다면 1 이상의 값이 나옵니다.
    Indexing[nr][nc][0] = idx;
    q.offer(new Node(nr, nc));
}

 

비트마스킹을 통해 벽을 판단하는 방법을 정했습니다.

 

이제는 해당 벽에 맞추어서 일반적인 BFS를 진행하면 됩니다.

이때, 0: 현재 방의 Index를 저장합니다. 1: 현재 방의 최대 카운트값을 저장합니다.

Indexing[][][2] 2차원 배열로 선언하여 위의 Indexing Group을 정하고, 방의 최대 카운트값 또한 [3.하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기] 을 구하기 위해 저장합니다.

    	Indexing = new int[M][N][2]; //0: 현재 방의 Index를 저장합니다. 1: 현재 방의 최대 카운트값을 저장합니다.

 

1. 이 성에 있는 방의 개수는 Indexing의 최대값으로 구할 수  있습니다.

2. 가장 넓은 방의 넓이는 BFS를 진행하며 가장 큰 BFS의 cnt값으로 갱신해갑니다.

3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기는 Indexing[][]2] 에서 모든 배열을 돌면서 만약 상하좌우의 Indexing Group이 다르다면, 벽에 막혀 있는것이므로 벽을 부수고 합칠 수 있습니다. 이떄 최대값으로 갱신합니다.

 

제가 실수했었던 부분은, 벽의 위치를 계산할때 현재 map의 위치에서 벽이 존재하는지 확인했어야했는데 이동한 방향의 벽을 계산하여서 오류가 있었습니다.

if( (map[temp.r][temp.c] & (1 << dir) ) == 0) { //만약 해당방향에 벽이 없다면, 이동시킨다. 만약 벽이 존재한다면 1 이상의 값이 나옵니다.
    Indexing[nr][nc][0] = idx;
    q.offer(new Node(nr, nc));
}

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M;
	public static int[][] map;
	public static int answer = Integer.MAX_VALUE;
	public static int[][][] Indexing;
	public static int idx = 1;
	public static int[] dx= {0, -1, 0, 1};
	public static int[] dy = {-1, 0, 1, 0};
	public static int answerRoomCnt = 0, answerMaxRoom = 0, answerBreakWallRoom = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
 
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	map = new int[M][N];
    	Indexing = new int[M][N][2]; //0: 현재 방의 Index를 저장합니다. 1: 현재 방의 최대 카운트값을 저장합니다.
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=0;i<M;i++) {
    		for(int j=0;j<N;j++) {
    			if(Indexing[i][j][0] == 0) {
    				simulate(new Node(i, j)); 
    			}
    		}
    	}
    	
//    	for(int i=0;i<M;i++) {
//    		for(int j=0;j<N;j++) {
//    			System.out.print(" "+Indexing[i][j][0]);
//    		}
//    		System.out.println();
//    	}
    	
    		
		for(int i=0;i<M;i++) {
			for(int j=0;j<N;j++) {
				getMaxWallBreakCount(new Node(i, j));
			}
		}
		answerRoomCnt = idx - 1; //1. 이 성에 있는 방의 개수
    	answerMaxRoom = answerMaxRoom; //2. 가장 넓은 방의 넓이. (simulate함수에서 구했었습니다.)
    	answerBreakWallRoom = answerBreakWallRoom; //3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
    	System.out.println(answerRoomCnt);
    	System.out.println(answerMaxRoom);
    	System.out.println(answerBreakWallRoom);
	}
	
	public static void simulate(Node start) {
		Queue<Node> q = new LinkedList<>();
		List<Node> storeVisitedRoom = new LinkedList<Node>();
		int roomCnt = 0;
		Indexing[start.r][start.c][0] = idx;
		q.offer(start);
		while(!q.isEmpty()) {
			Node temp = q.poll();
			roomCnt += 1;
			storeVisitedRoom.add(temp);
			for(int dir = 0; dir < 4; dir ++) {
				int nr = temp.r + dx[dir];
				int nc = temp.c + dy[dir];
				if(nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
				if(Indexing[nr][nc][0] != 0 ) continue;
				
				if( (map[temp.r][temp.c] & (1 << dir) ) == 0) { //만약 해당방향에 벽이 없다면, 이동시킨다. 만약 벽이 존재한다면 1 이상의 값이 나옵니다.
					Indexing[nr][nc][0] = idx;
					q.offer(new Node(nr, nc));
				}
				
			}
		}
		
		for(int i=0;i<storeVisitedRoom.size();i++) { //해당 그룹의 벽 개수를 전체 그룹에 모두 동기화시킵니다.
			Node temp = storeVisitedRoom.get(i);
			Indexing[temp.r][temp.c][1] = roomCnt; 
		}
		
		answerMaxRoom = Math.max(answerMaxRoom, roomCnt);
		idx += 1;//방의 인덱싱 1개 증가시킵니다.
	}
	
	public static void getMaxWallBreakCount(Node start) {
		Node temp = start;
		for(int dir = 0; dir<4; dir++) {
			int nr = temp.r + dx[dir];
			int nc = temp.c + dy[dir];
			
			if(nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
			if(Indexing[nr][nc][0] != Indexing[temp.r][temp.c][0]) { //만약 인덱싱이 옆과 다르다면 해당 벽을 부순뒤 합칩니다.
				answerBreakWallRoom = Math.max(answerBreakWallRoom, Indexing[nr][nc][1] + Indexing[temp.r][temp.c][1]);
			}
		}
	}
	
	
}
 
class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}