[백준 2234]bfs : 성곽(java) - 비트마스킹

문제보러가기

2234번: 성곽

 

이 문제는 기존 bfs처럼 영역을 나눠서 영역의 개수, 영역의 최대 넓이 , 벽을 하나 제거한 후의 영역의 최대 넓이를 구하는 여러 문제가 합쳐져 있는 복합적인(?) 문제였다. 여기서 까다롭게 봐야 할 점은 벽을 제시할 때 0~15의 값으로 주어지며 이를 bit로 변환하여 사용해야 한다는 점이었다.

 

 

 

 

 

 

문제풀이

- bfs로 구한 영역을 증가하는 groupCnt를 키값으로 묶어  아래 그림처럼 group [][]에 저장해준다.

group[][] 배열

-bfs로 영역을 구할 때 벽을 구해야 하는데 0~15로 방향을 나타내게 된다.

1 : 서 , 2 : 북,  4 : 동, 8: 남을 기준으로 하며 만약 3일 경우는 1+2 즉, 서쪽 북쪽에 벽이 있다는 의미.

 

문제에도 나타나 있듯이 2진 비트를 생각하여 구하면 된다. 나는 아래와 같이 사용하였다.

3 -> 0011 -> 북, 서 

11 -> 1011 -> 남, 북, 서

결론=> 1번째 bit가 1일 경우 남쪽에 벽 , 2번째 bit가 1일 경우 동쪽에 벽...

이걸 이용하여 주어진 칸의 숫자를 ->2진 비트로 변환 -> 남동 북서 순서로 확인하며 진행하였다.

*1이 서쪽부터 시작하는데 왜 남쪽부터 하냐고 생각할 수 있다 (4bit를 기준으로 하므로 비트의 맨 앞 순서가 8을 나타내기 때문!)

 

-bfs로 영역을 구할 때 동시에 HashMap에 groupCnt로 각각 영역의 넓이를 저장하면서 진행한다. 이렇게 되면 영역의 개수와 넓이를 동시에 구할 수 있다.

 

-HashMap에 저장되어 있는 영역의 번호(groupCnt)와 영역의 넓이를 이용하여 하나의 벽을 뚫었을 때 최대 넓이를 구한다.

 

-위의 bfs에 이용했던 벽을 구하는 방법으로 이번에는 벽을 지우고 붙어있는 영역의 합을 구하면 된다.

 

 

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Ex_2234 {

	static int[][] arr;
	static int[][] group;
	static Map<Integer, Integer> map;
	static int removeWallSize;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub

		// bfs 성곽
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		arr = new int[m][n];
		group = new int[m][n];
		map = new HashMap<>();
		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());
			}
		}
		int groupCnt = 1;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (group[i][j] == 0) {
					int cnt = bfs(i, j, groupCnt);
					max = Math.max(max, cnt);
					map.put(groupCnt, cnt);
					groupCnt++;					
				}
			}
		}
		for(int i=0;i<m;i++) {
			for(int j=0;j<n;j++) {
				removeWall(i,j);
			}
		}
		System.out.println(map.size());//방개수
		System.out.println(max);//가장 넓은 방
		System.out.println(removeWallSize);//하나의 벽 제거하여 얻는 가장 넓은 방
	}

	//비트를 구해서 스트링으로 반환
	static String getBit(int n) {
		StringBuilder sb = new StringBuilder();
		while (n != 0) {
			sb.append(String.valueOf(n % 2));
			n /= 2;
		}
		while (sb.length() < 4) {
			sb.append("0");
		}
		return sb.reverse().toString();
	}

	//벽을 하나 지우고 연결된 영역의 값 구하기
	static void removeWall(int x, int y) {
		int sum = map.get(group[x][y]);
		int[] dx = { 1, 0, -1, 0 };
		int[] dy = { 0, 1, 0, -1 };
		
		String bit = getBit(arr[x][y]);
		
		for (int i = 0; i < 4; i++) {
			
			int sx = x+dx[i];
			int sy = y+dy[i];
			
			if(sx < 0 || sy < 0|| sx >= arr.length || sy >= arr[0].length)
				continue;
            //벽이고 같은 영역 그룹에 속하지 않았을 경우
			if (bit.charAt(i) == '1' && group[x][y]!=group[sx][sy]) {
				sum+=map.get(group[sx][sy]);
                //벽을 하나 지운 후의 최대 영역 넓이를 갱신
				removeWallSize = Math.max(removeWallSize, sum);
				sum-=map.get(group[sx][sy]);
			}
				
		}
		
	}
    //영역을 묶고 개수를 map에 저장함
	static int bfs(int x, int y, int groupCnt) {
		int cnt = 1;
		Queue<Room> q = new LinkedList<>();
		q.add(new Room(x, y));
		group[x][y]=groupCnt;
		
		int[] dx = { 1, 0, -1, 0 };
		int[] dy = { 0, 1, 0, -1 };
		while (!q.isEmpty()) {

			Room r = q.poll();
            //비트로 변환된 값을 가져옴
			String bit = getBit(arr[r.x][r.y]);
			
			for (int i = 0; i < 4; i++) {
				int sx = r.x+dx[i];
				int sy = r.y+dy[i];
				//벽이면 더이상 갈 수 없으니 반복문으로 돌아감
				if (bit.charAt(i) == '1') 
					continue;
                //그룹에 속하지 않았던 영역이라면 그룹으로 묶음
				if(group[sx][sy]==0) {
					group[sx][sy]= groupCnt;
					cnt++;
					q.add(new Room(sx,sy));
				}
				
			}
		}

		return cnt;
	}
}

class Room {
	int x;
	int y;

	Room(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

* 참고로 java에는 bit를 구할 수 있는 Integer.toBinaryString() 함수를 제공한다!