비트마스킹

비트마스킹은 정수의 이진수 표현을 활용해 집합이나 상태를 효율적으로 표현하고 조작하는 기법이다.

핵심 아이디어

정수 하나의 각 비트를 켜짐/꺼짐 플래그로 사용하는 방법이다.

예를 들어 원소가 {0, 1, 2, 3} 인 집합에서 부분집합 {0, 2} 는 이진수 0101, 즉 정수 5로 표현할 수 있다.

기본 연산

1. 특정 비트 켜기 (원소 추가)mask |= (1 << i) — i번째 비트를 1로 설정

2. 특정 비트 끄기 (원소 제거)mask &= ~(1 << i) — i번째 비트를 0으로 설정

3. 특정 비트 확인 (원소 포함 여부)if (mask & (1 << i)) — i번째 비트가 1인지 검사

4. 특정 비트 토글mask ^= (1 << i) — i번째 비트를 반전

5. 집합 연산 합집합은 a | b, 교집합은 a & b, 차집합은 a & ~b로 계산

왜 쓰는가

배열이나 set으로 부분집합을 관리하면 메모리도 많이 쓰고 연산도 느린데, 비트마스크를 쓰면 정수 하나로 최대 64개 원소의 부분집합을 표현할 수 있고, 집합 연산이 O(1)에 끝난다. DP에서 상태를 표현할 때 특히 뛰어나다.

대표적인 활용 예시

비트마스크 DP (외판원 문제 등)

c++

// dp[mask][v] = mask에 포함된 도시들을 방문하고 현재 v에 있을 때의 최소 비용
// mask의 i번째 비트가 1이면 도시 i를 이미 방문했다는 뜻

for (int mask = 0; mask < (1 << n); mask++) {
    for (int v = 0; v < n; v++) {
        if (!(mask & (1 << v))) continue; // v가 mask에 없으면 skip
        for (int u = 0; u < n; u++) {
            if (mask & (1 << u)) continue; // u를 이미 방문했으면 skip
            int next = mask | (1 << u);
            dp[next][u] = min(dp[next][u], dp[mask][v] + dist[v][u]);
        }
    }
}

한계

시간복잡도 면에서 n개 원소의 모든 부분집합은 2^n개라서, 보통 n ≤ 20 정도일 때 비트마스크 DP를 적용할 수 있다.

#2098 외판원 순회

비트마스크 DP의 상태는 dp[현재 도시][방문한 도시들의 집합]으로 정의한다. 여기서 방문한 도시들의 집합을 정수 하나의 이진수 표현으로 나타낸다.

visited 변수는 각 비트가 해당 도시의 방문 여부를 나타낸다. 예를 들어 visited = 0101이면 도시 0과 2를 방문한 상태를 의미한다.

초기 호출은 tsp(n, 0, 1)로 시작한다. 1은 이진수 0001이므로 0번 도시만 방문한 상태에서 출발한다는 뜻이다.

종료 조건은 visited == (1 << n) - 1로 확인한다. 모든 비트가 1이면 모든 도시를 방문한 것이므로, 출발점으로 돌아가는 비용 w[start][0]을 리턴한다.

이미 방문한 도시인지는 visited & (1 << i)로 검사한다. i번째 비트가 켜져 있으면 이미 방문한 도시이므로 건너뛴다.

다음 상태로의 전이는 visited | (1 << i)로 수행한다. 기존 방문 집합에 도시 i를 추가한 새로운 집합을 만든다.

메모이제이션은 dp[start][visited] != -1로 확인한다. 이미 계산한 상태면 저장된 값을 바로 리턴하여 중복 계산을 방지한다.

시간복잡도는 O(n² × 2^n)이다. 상태 수가 n × 2^n개이고 각 상태에서 최대 n개의 도시를 탐색하기 때문이다.

c++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> w;
vector<vector<int>> dp;

int tsp(int n, int start, int visited) {
    if (visited == (1 << n) - 1) {
        if (w[start][0] == 0) return -1;
        return w[start][0];
    }

    if (dp[start][visited] != -1) {
        return dp[start][visited];
    }

    dp[start][visited] = 1e9;
    for(int i = 0 ; i < n ; i++) {
        if(w[start][i] == 0 || (visited & (1 << i))) continue;
        int next = tsp(n, i, visited | (1 << i));
        if(next != -1) {
            dp[start][visited] = min(dp[start][visited], next + w[start][i]);
        }
    }
    return dp[start][visited] == 1e9 ? -1 : dp[start][visited];
}

int main() {
    int n;
    cin >> n;
    w.resize(n, vector<int>(n));
    dp.resize(n, vector<int>(1 << n, -1));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> w[i][j];
        }
    }

    cout << tsp(n, 0, 1) << endl;
}