비트마스킹 DP

비트마스킹을 이용해 DP문제를 풀어봅시다.

 

\(n\)크기의 집합이 있을 때, 이 집합의 서로 다른 부분집합의 개수는 \(2^n\)가지 입니다.

그리고 이 부분집합들을 하나의 정수로 쉽게 변환할 수 있습니다. 어떻게 하면 될까요?

 

5개의 원소를 가진 집합 \(S\)가 있다고 가정해봅시다.

\(S = \{1,2,3,4,5\}\)

 

\(S\)의 모든 부분집합에 대해서, 각 원소가 존재하지 않으면 \(0\), 존재하면 \(1\)을 차례대로 써 넣어봅시다.

그러면 서로 다른 5자리 이진수가 될 텐데, 이 수를 보통의 10진수로 변환하면 \([0,15]\)의 범위를 가지는 서로 다른 수로 변환됩니다.

 

원소의 수가 32개 이하라면 int범위에, 64개 이하라면 long long 범위에 저장할 수 있고,

만약 원소의 수가 이보다 많은 집합을 이러한 형태로 저장하려면 bitset을 이용하면 됩니다.

 

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

11723번: 집합

부분집합을 하나의 정수로 변환시키는 법을 알았으니, 이 집합에 다양한 연산을 해 봅시다.

 

집합을 나타내는 정수를 2진수로 변환했을 때 하나의 비트는 하나의 원소를 나타냅니다.

따라서 원소의 추가/삭제/수정 등을 간단한 비트연산으로 빠르게 할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int st = 0;
 
    int m; cin >> m;
    while (m--)
    {
        string s; cin >> s;
 
        if (s == "add")
        {
            int x; cin >> x;
            st |= (1 << x - 1);
        }
        else if (s == "remove")
        {
            int x; cin >> x;
            st &= ~(1 << x - 1);
        }
        else if (s == "check")
        {
            int x; cin >> x;
            cout << (st & (1 << x - 1) ? 1 : 0) << '\n';
        }
        else if (s == "toggle")
        {
            int x; cin >> x;
            st ^= (1 << x - 1);
        }
        else if (s == "all")
        {
            st = (1 << 20) - 1;
        }
        else if (s == "empty")
        {
            st = 0;
        }
    }
}

---

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

2098번: 외판원 순회

비트마스킹을 배웠으니, 이를 이용한 DP문제를 풀어봅시다.

 

DP식을 다음과 같이 정의해봅시다.

\(DP(i, st) : \) 지금까지 집합 st에 포함된 도시들을 방문했고, 현재 i번째 도시에 있을 때 순회 비용의 최소값

 

여기에서 \(st\)에 실제 set등의 집합을 넣는 대신, 비트마스킹으로 표현한 하나의 정수를 넣을 수 있게 됩니다.

원소가 \(n\)개인 집합의 부분집합을 모두 표현할 수 있어야 하므로, \(st\)의 범위는 \(0 \le st \lt 2^n\)입니다.

 

그러면 다음과 같은 점화식을 얻을 수 있습니다.

\(DP(i, st) = min_{j \notin st}\{DP(j, st \cup \{j\}) + cost(i, j)\}\)

 

총 \(n \cdot 2^n\)가지의 상태가 있고, 각 상태마다 \(n\)가지의 부분 문제를 계산해야 합니다.

따라서 시간복잡도는 \(O(n^2 \cdot 2^n)\)이고, \(n \le 16\)이므로 시간 안에 충분히 들어옵니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int cost[16][16];
 
int dp[16][1 << 16];
int solve(int idx, int st)
{
    // 지금까지 집합 st가 나타내는 도시를 방문했고, 현재 idx번째 도시에 있다.
    // 시작 도시는 first이다.
 
    int& ret = dp[idx][st];
    if (ret != -1) return ret;
 
    if (st == (1 << n) - 1)
    {
        if (cost[idx][0]) return ret = cost[idx][0];
        else return ret = 987654321;
    }
        // st가 전체집합이면 이미 순회를 끝낸것이다.
 
    ret = 987654321;
    for (int i = 0; i < n; i++)
    {
        if (cost[idx][i] == 0) continue;
        if (st & (1 << i)) continue;
        // 길이 없거나 이미 방문한 도시는 무시한다.
 
        int res = solve(i, st | (1 << i)) + cost[idx][i];
        // i번째 도시로 이동하고 집합 st에 i를 추가한다.
 
        ret = min(ret, res);
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        cin >> cost[i][j];
 
    memset(dp, -1, sizeof dp);
 
    int ans = solve(0, 1);
    // 0번 도시부터 시작한다.
 
    cout << ans;
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217