비트연산자

1. 비트연산자

1) & : 비트가 둘다 1인 경우만 결과가 1 나온다.

2) | : 비트가 하나라도 1인 경우 결과가 1 나온다

3) 1 << num : 1을 num만큼 왼쪽으로 num만큼 이동한다

2. 알고리즘에서 사용하는 방법

1) 비트마스크를 사용한 부분집합구하기

public class Fruits {
	public static void main(String[] args) {
		String fruits[] = {"사과", "배", "바나나"};
		for (int i = 0; i < (1<<fruits.length) ; i++) {//모든 부분집합을 구한다 2의3승
			for (int j = 0; j < fruits.length; j++) {//각 자리마다 1이 존재하는지 탐색
				if((i & (1<<j)) != 0) {
					System.out.print(fruits[j]+" ");
				}
			}
			System.out.println();
		}
	}
}

2) 순열에서 방문 체크 배열을 비트마스크로 바꾸기

static int arr[];
static int visit, N;
static void perm(int idx) {
	//끝까지 간 경우
	if(idx == N) {
		return;
	}
	for (int i = 0; i < arr.length; i++) {
		if((visit & (1<<i)) ==0 ) {
			visit = visit | (1<<i);
			perm(idx+1);
			visit = visit & ~(1<<i);
		}
	}
}

3. 비트마스크 응용

 

1) 큐에서 배열을 가지고 다녀야 하는 경우가 있다. 이때 char배열을 가지고 다니면 메모리초과가 나기 때문에,

비트마스크를 활용하여 메모리초과를 막을 수 있다.

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

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

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

public class Main {
	static class Pair {
		int r, c, key,dist;

		public Pair(int r, int c, int key,int dist) {
			this.r = r;
			this.c = c;
			this.key = key;
			this.dist = dist;
		}
	}
	static int n,m,res=-1;
	static char map[][];
	static boolean visit[][][]; // 열쇠를 소유한 상태가 z축
	static int dr[] = { -1, 0, 1, 0 };
	static int dc[] = { 0, 1, 0, -1 };
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine()," ");
		n = Integer.valueOf(st.nextToken());
		m = Integer.valueOf(st.nextToken());
		map = new char[n][m];
		visit = new boolean[1<<6][n][m];
		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < str.length(); j++) {
				map[i][j] = str.charAt(j);
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(map[i][j] == '0') {//시작점
					bfs(i,j);				
					break;
				}
			}
		}
		System.out.println(res);
	}
	static void bfs(int y, int x) {
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(y,x,0,0));
		visit[0][y][x]=true;
		while(!q.isEmpty()){
			Pair cur = q.poll();
			if(map[cur.r][cur.c]=='1') {
				res = cur.dist;
				break;
			}
			for (int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				if(nr < 0 || nr>= n || nc <0 ||nc>=m)
					continue;
				if(visit[cur.key][nr][nc])
					continue;
				if(map[nr][nc]=='#')
					continue;
				if(map[nr][nc]>='a' && map[nr][nc]<='f') {
					int newKey = cur.key | (1 << map[nr][nc]-97);
					visit[newKey][nr][nc] = true;
					q.add(new Pair(nr,nc,newKey, cur.dist+1));
				}
				if(map[nr][nc]>='A' && map[nr][nc]<='F') {
					if( (cur.key & (1<<map[nr][nc]-65)) !=0 ){//키가 존재한다면
						visit[cur.key][nr][nc] = true;
						q.add(new Pair(nr,nc,cur.key, cur.dist+1));
					}
				}
				else{
					visit[cur.key][nr][nc] = true;
					q.add(new Pair(nr,nc,cur.key, cur.dist+1));
				}
			}
		}
	}
}
/*
!!!!!열쇠를 소유한 상태가 다르다!!!!!!
0부터 시작 -> 소문자를 집는다 -> 소문자를 | 연산 -> 대문자는 &로 비교 참거짓판단 -> 1까지간다

큐에넣고
	빌때까지
		4방탐색
			맵이탈
			열쇠면		
*/