비트마스크 개요

알고리즘이라기 보다는 일종의 테크닉이다. 기본적으로 컴퓨터는 데이터를 이진수로 저장하므로 비트단위로 데이터를 보겠다는 것이다. 그렇다면 비트연산을 쓰는 이유는 무엇일까? 장점을 적어보면 다음과 같다.

1. 삽입, 삭제, 검색 기능이 간결해진다.
2. 빠른 연산 속도, 적은 메모리로 상태 표현이 가능하다.
3. 다이나믹 프로그래밍. (매우 중요!)

정수를 원소로 하는 집합을 생각하자. 원소가 있다면 1(true), 없으면 0(false)라고 생각할 수 있다.

int my_set = {1, 1, 0, 0, 1};

그런데 원소가 많다면 메모리를 많이 차지하고, 더욱 중요한것은 집합의 연산을 할때 오버헤드가 매우 크다는 것이다.(변화하는 상태마다 이 데이터를 복사해야한다.) 하지만 비트로 표현하면 간단하게 표현할 수 있다.

int bit = 19; // 19 = 1 + 2 + 16

여기서 2번째(인덱스가) 원소를 추가하는 연산을 한다고 하자.

bit = 23; // 1 + 2 + 4 + 16

아니 그런데 2번째 원소를 추가하는것을 내가 일일이 2진수로 변환하느니 배열을 쓰겠다? 그렇지 않다. 컴퓨터는 기본적으로 비트연산을 제공한다. 아래 연산을 보고 코드에 적용해보자.

비트연산

1. AND, OR, XOR, NOT

AND는 &, OR는 |, XOR은 ^로 연산한다. (논리연산자의 &&, ||와 다르다) 그리고 NOT은 ~으로 연산한다. (논리연산이 아니므로 !가 아니다)

1010 & 1111 = 1010 # 둘다 1이어야 1
1010 | 1111 = 1111 # 하나라도 1이어야 1
1010 | 1111 = 0101 # 다를 때 1
~1010 = 0101

2. SHIFT

SHIFT연산을 통해 비트를 왼쪽, 오른쪽으로 밀어낼 수 있다. 이때 버려지는 채워지는 비트는 0으로 채워진다. (rotation shift가 아니다)
<<, >> 로 왼쪽, 오른쪽으로 shift연산을 할 수 있다.

00000001 << 2 = 00000100
10000000 >> 3 = 00010000

shift연산을 통해 2배 곱하기, 2배 나누기 연산을 할 수 있다.

비트연산의 실제 이용

집합에 원소가 있다면 1, 없다면 0으로 데이터를 저장하자. 처음에는 아무것도 없는 집합이므로 0이다.

int bit = 0;

원소의 추가

n번째 원소를 추가한다. 즉 n번째 비트가 1이 되고, 나머지는 원래 상태가 변하지 않는다. OR연산을 이용한다.

// 아래 두 식은 같은 표현이다
bit = bit | (1 << n);
bit |= 1 << n; 

원소의 삭제

n번째 원소를 삭제한다. 즉 n번째 비트가 0이 되고, 나머지는 원래 상태가 변하지 않는다. AND 연산을 이용한다.
n = 3이고, bit = 11110이라면 bit = 10110이 되면 된다.

bit = bit & ~(1 << n);

원소의 검색(존재성)

n번째 원소가 존재하는지 확인한다. n번째 비트가 1이라면 존재하고, 0이라면 존재하지 않는다. AND연산을 이용한다.

exist = bit & (1 << n);

[BOJ 11723] 집합

toggle연산은 XOR연산을 이용하면 된다.
나머지 연산은 위에 나온 것을 이용하면된다.

bits = bits ^ (1 << x);

[BOJ 2098] 외판원 순회

모든 경우의 수를 따지면 $O(n!)$이다. 따라서 $O(16!)$이고 시간초과가 나는 경우이다.
외판원이 방문한 도시를 visit로 상태를 저장한다. 모든 도시를 저장하는 것은 비효율적이므로 비트마스크를 이용한다.
i번째 도시를 방문하면 다음처럼 처리한다.

visit = visit | (1 << i);

i번째 도시를 방문했는지 확인여부는 다음처럼 처리한다.

check = visit & (1 << i)

check가 1이라면 이미 방문했다는 뜻이고, 0이라면 방문하지 않았다는 뜻이 된다.

총 16개의 도시가 있으므로 최대 상태표현은 $2^{16}$=1 << 16이다.
나는 여유롭게 1 << 20개 만큼 공간을 할당하였다.

#include <stdio.h>
#include <algorithm>
using namespace std;

int N;
int sale[20][20];
int dp[20][1 << 20];

int TSP(int cur, int visit) {
	// Salesman has visited ALL city
	if (visit == (1 << N) - 1) {

		// add cost of last->start 
		// I started from 0_th city (see the main())
		if (sale[cur][0] > 0) return sale[cur][0];
		
		// visited all city, but cannot reach the start city(0_th city)
		else return 2 * 1e7;
	}


	int& ret = dp[cur][visit];
	
	// already visit
	if (ret > 0) return ret;
	
	// setting INF
	ret = 2*1e7;


	for (int i = 0; i < N; i++) {
		// visit & (1 << i) : check if salesman has visited i_th city
		// sale[cur][i] : cost from cur to i_th city
                // visit | (1 << i) :: visit i_th city
		if (!(visit & (1 << i)) && sale[cur][i]) {
			ret = min(ret, TSP(i, visit | (1 << i)) + sale[cur][i]);
		}
	}
	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &sale[i][j]);
		}
	}

	// start from 0_th city
	printf("%d", TSP(0, 1));

	return 0;
}