[알고리즘] 비트마스크(BitMask) 스킬 숙련하기(feat. 백준 1194 달이 차오른다, 가자.)

백준 1194 달이 차오른다, 가자 를 풀면서 방문 체크를 도대체 어떤 식으로

해줘야 할까라는 고민에 빠지게 되었다..

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

1194번: 달이 차오른다, 가자.

a~f까지의 열쇠를 어떻게 해주어 하냐 했는데,

비트 마스킹을 이용해 보라는 조언을 받았다..

들어는 봤는데 자세히는 몰라서 한번 공부를 해보자 라는 생각으로

이번 블로그 포스팅을 쓴다..

그럼 시작해볼까?

 

---

비트 마스크(BitMask) 란?

정수의 이진수 표현을 활용하여 다양한 로직에 활용하는 기법이라고 할 수 있다. 

비트 마스크를 사용하면 더 빠른 수행 시간과 메모리 사용량을 줄일 수 있습니다. 

 

위의 문제에서 a부터 f의 키의 보유상황을 구현을 해보자.

먼저 첫 번째 방법으로 배열의 인덱스를 이용해서 구해보자.

 

{a, b, c},

{a, c, d},

{b, d},

{a}....

길이 6의 boolean 배열을 선언하여

 

boolean [] visited = {true, true, true, false, false, false}; // {a, b, c}

boolean [] visited = {true, false, true, true, false, false}; // {a, c, d}

boolean [] visited = {false, true, false, true, false, false}; // {b, d}

boolean [] visited = {true, false, false, false, false, false}; // {a}

 

처럼 나타낼 수도 있을 것이다. 하지만 메모리가 커지게 되는 치명적인 단점이 있고, 번거로운 구현 과정이 있을 것이다.

이러한 점을 간단하게 해결할 수 있는 것이 비트 마스크이다.

 

{a, b, c} --> 111000

{a, c, d} --> 101100

{b, d} --> 010100

{a} --> 100000

 

이런 식으로 나타낼 수 있게 된다.

비트 마스크를 이해하기 위해 비트 연산을 소개해보도록 하겠다.

 

비트 연산

And 연산(&)

대응하는 두 비트가 모두 1일 때, 1을 반환.

-> 1100 & 1000 = 1000

 

or 연산(|)

대응하는 두 비트가 적어도 한 개가 1일 때, 1을 반환.

-> 1100 | 1000 = 1100

 

xor 연산(^)

대응하는 두 비트가 서로 다르면 1을 반환.

-> 1100 ^ 1000 = 0100

 

시프트 연산(>>, <<)

왼쪽 또는 오른쪽으로 비트를 옮긴다.

-> 1100 << 2 = 110000

-> 10110 >> 1 = 1011

---

풀이 방법

bfs를 이용하여 완전 탐색을 하였고, 그 과정에서 비트 마스크를 이용한 방문처리를 활용해주었다. 

알파벳에 해당하는 열쇠가 있어야 들어갈 수 있기 때문에, 비트마스크 기법을 이용하여 열쇠의 유무를 확인해주었다.

코드

package Baekjoon2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Baekjoon_1194_달이차오른다가자 {
	static int R, C;
	static char[][] arr;
	static boolean[][][] visited;
	static int[][] search = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine());
		R = Integer.parseInt(token.nextToken());
		C = Integer.parseInt(token.nextToken());
		arr = new char[R][C];
		Point start = new Point(0, 0, 0);
		for (int r = 0; r < R; r++) {
			String str = br.readLine();
			for (int c = 0; c < C; c++) {
				arr[r][c] = str.charAt(c);
				if (arr[r][c] == '0') {
					start = new Point(r, c, 0);
				}
			}
		}

		visited = new boolean[R][C][1 << 6];
		System.out.println(bfs(start));
	}

	private static int bfs(Point start) {
		Queue<Point> queue = new LinkedList<>();
		queue.offer(start);
		visited[start.r][start.c][start.key] = true;
		int time = 1;
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				Point top = queue.poll();

				for (int s = 0; s < search.length; s++) {
					int nr = top.r + search[s][0];
					int nc = top.c + search[s][1];
					int key = top.key;

					if (isIn(nr, nc) && arr[nr][nc] != '#') {
						if (arr[nr][nc] == '1') {
							return time;
						}

						if (arr[nr][nc] <= 'f' && arr[nr][nc] >= 'a') {
							key = key | (1 << arr[nr][nc] - 'a');
						}
						if (arr[nr][nc] <= 'F' && arr[nr][nc] >= 'A') {
							if ((key & (1 << arr[nr][nc] - 'A')) == 0) {
								continue;
							}
						}
						if (visited[nr][nc][key]) {
							continue;
						}
						visited[nr][nc][key] = true;
						queue.offer(new Point(nr, nc, key));

					}
				}
			}
			time++;
		}
		return -1;
	}

	static boolean isIn(int r, int c) {
		return r >= 0 && c >= 0 && r < R && c < C;
	}

	static class Point {
		int r, c, key;

		public Point(int r, int c, int key) {
			super();
			this.r = r;
			this.c = c;
			this.key = key;
		}

		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + ", key=" + key + "]";
		}

	}
}

---

결론

비트마스크를 말로만 듣고 지레 겁을 먹곤 했는데 해보니까 딱히 별거 없었다. 그러니까 다들 문제를 풀어보고 비트마스크 기법을 익혀보는 것을 추천한다.

코로나가 얼른 종식되길 바라면서 모두 파이팅하길 바란다!!