[C++] 비트마스크(BitMask)

비트마스크(BitMask)

집합 요소들의 구성 여부를 표현할 때 유용한 테크닉이다.

 

기본 원리

{1, 2, 3, 4, 5}라는 집합이 있고 이 집합의 부분집합을 구해야 한다.

{1}, {2}, ..., {1, 2}, ..., {1, 2, 5}, ..., {1, 2, 3, 4, 5}

 

물론 간단히 반복문을 통해 경우의 수를 구할 수 있다.

하지만 비트 마스킹을 하면 각 요소를 인덱스처럼 표현하여 효율적인 접근이 가능하다.

{1, 2, 3, 4, 5} → 11111
{2, 3, 4, 5} → 11110
{1, 2, 5} → 10011
{2} → 00010

 

1) 삽입

i번 째 비트 값을 1로 변경하려고 한다. 이때 OR 연산을 활용한다.

i = 3일 때, 10101 | (1 << 3) → 10101 | 01000 → 11101

 

2) 삭제

i번 째 비트 값을 0으로 변경하려고 한다. 이때 AND 연산과 NOT 연산을 활용한다.

i = 3일 때, 11101 & (~1 << 3) → 11101 & 10111 → 10101

 

3) 조회

i번째 비트가 무슨 값인지 알려면 AND 연산을 활용한다.

10101 & (1 << i) → 0이면 i번째 비트 값이 0이다.

 

문제

 

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

2098번: 외판원 순회

#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1e9;

int N;
int W[16][16];
int dp[16][1 << 16];

int DFS(int cur, int visited)
{
	int& ret = dp[cur][visited];
	if (ret > 0)
		return ret;

	if (visited == (1 << N) - 1) { // 모든 도시를 다 방문함
		// 순회: 다시 0번째 도시로 돌아간다.
		if (W[cur][0] != 0)
			return W[cur][0];
		return INF;
	}

	ret = INF;
	for (int i = 0; i < N; i++)
		if (W[cur][i] && !(visited & (1 << i)))
			ret = min(ret, W[cur][i] + DFS(i, visited | (1 << i)));
	return ret;
}

int main()
{
	cin >> N;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			cin >> W[y][x];
	cout << DFS(0, 1);
	return 0;
}

 

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

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

#include <iostream> 
#include <algorithm>
#include <queue>
using namespace std;

int N, M;
char map[50][50];
bool visited[50][50][1 << 6];
int dir[4][2]{ {0,-1},{0,1},{-1,0},{1,0} };

typedef struct {
	int x, y, cnt, key;
}Point;

int bfs(Point start)
{
	queue<Point> q;
	q.push(start);
	visited[start.x][start.y][start.key] = true;

	while (!q.empty()) {
		Point cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dir[i][0], ny = cur.y + dir[i][1];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] == '#' || visited[nx][ny][cur.key])
				continue;

			if (map[nx][ny] == '1')	// 출구
				return cur.cnt + 1;
			else if (map[nx][ny] == '.') {
				q.push({ nx, ny, cur.cnt + 1, cur.key });
				visited[nx][ny][cur.key] = true;
			}
			else if ('a' <= map[nx][ny] && map[nx][ny] <= 'f') {	// 열쇠
				int key = 1 << (map[nx][ny] - 'a');
				q.push({ nx, ny, cur.cnt + 1, cur.key | key });
				visited[nx][ny][cur.key | key] = true;
			}
			else if ('A' <= map[nx][ny] && map[nx][ny] <= 'F') {	// 문
				int door = 1 << (map[nx][ny] - 'A');
				if (cur.key & door)
				{
					q.push({ nx, ny, cur.cnt + 1, cur.key });
					visited[nx][ny][cur.key] = true;
				}
			}
		}
	}

	return -1;
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	Point start{};
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] == '0') {
				start = { i, j, 0, 0 };
				map[i][j] = '.';
			}
		}
	}

	cout << bfs(start);
}

 

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

1102번: 발전소

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int N, P;
int machine[16][16];
int dp[1 << 16];

int GetOnCount(int n)
{
    if (n == 0)
        return 0;
    return GetOnCount(n >> 1) + (n & 1);
}

int GetMinCost(int state)
{
    int& result = dp[state];

    if (result != -1)
        return result;
    if (GetOnCount(state) >= P)
        return 0;

    result = 1e9;

    for (int i = 0; i < N; i++)
        if ((state & (1 << i))) { // 작동 중인 발전기(on)
            for (int j = 0; j < N; j++) {
                if ((state & (1 << j)) == 0) { // 고장난 발전기(off)
                    // on 발전기가 off 발전기 작동
                    result = min(result, machine[i][j] + GetMinCost(state | (1 << j)));
                }
            }
        }

    return result;
}

int main()
{
    string onoff;

    cin >> N;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> machine[i][j];
    cin >> onoff >> P;

    int on = 0; // 현재 작동 중인 발전기 넘버 비트 저장
    for (int i = 0; i < N; i++)
        if (onoff[i] == 'Y')
            on |= (1 << i); // i번째 비트에 1(on) 삽입

    if (GetOnCount(on) >= P)
    {
        cout << 0;
        return 0;
    }

    memset(dp, -1, sizeof(dp));
    int result = GetMinCost(on);
    if (result == 1e9)
        cout << -1;
    else
        cout << result;
}

 

https://programmers.co.kr/learn/courses/30/lessons/92343

코딩테스트 연습 - 양과 늑대

#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

#define MAX_STATE 17

struct Point {
    int index, state, ship, wolf;
};

vector<int> graph[MAX_STATE];
bool visited[MAX_STATE][1 << MAX_STATE];

int solution(vector<int> info, vector<vector<int>> edges)
{
    int answer = 0;

    for (auto edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }

    queue<Point> q;
    q.push({ 0,1,1,0 });
    visited[0][1] = true;
    while (!q.empty()) {
        Point curr = q.front();
        q.pop();
        answer = max(answer, curr.ship);

        for (int next : graph[curr.index]) {
            int nstate = curr.state | (1 << next);
            if (visited[next][nstate])
                continue;

            int ns = 0, nw = 0;
            if (!(curr.state & (1 << next))) {
                if (info[next]) { // 늑대
                    if (curr.ship <= curr.wolf + 1)
                        continue;
                    nw = 1;
                }
                else { // 양
                    ns = 1;
                }
            }

            visited[next][nstate] = true;
            q.push({ next,nstate,curr.ship + ns,curr.wolf + nw });
        }
    }

    return answer;
}