비트마스크 DP (Bitmask DP)

정의

비트마스크 DP (Bitmask DP) 는 상태 공간이 부분집합 으로 표현될 때, 각 부분집합을 정수의 비트로 인코딩해 DP 상태로 삼는 기법. N ≤ 20 범위에서 O(2^N × poly(N)) 복잡도로 조합 최적화를 푸는 표준 패턴.

대표 문제: 외판원 순회 (TSP), 집합 커버, 배치 최적화, 조합 카운팅.

문제 상황과 동기

상태 = “방문한 노드 집합 + 현재 노드” 같은 구조.

• naive: 모든 순열 O(N!) 탐색. N=20 이면 2.4 × 10^18, 불가능.
• bitmask DP: 집합 ⊆ {0, ..., N-1} 을 정수 mask ∈ [0, 2^N) 로 인코딩, dp[mask][i] = “mask 에 방문했고 지금 i 위치일 때의 최적값”. O(2^N × N^2), N=20 기준 ~100M 연산, 실행 가능.

핵심 통찰: 부분집합을 비트로 표현하면 포함 여부는 O(1) 비트 연산 (mask & (1 << k) / mask | (1 << k)), 순회도 O(N). 2^N × N^2 이하면 시간 안에 돌 수 있다.

자주 등장하는 컨텍스트:

• PS: TSP, 해밀턴 경로, 집합 분할 최소화, 조합 카운팅 (N ≤ 20 한정)
• 실무: constraint satisfaction, 스케줄링 (작은 N)

시각화

핵심 아이디어

비트 연산 기초:

mask |  (1 << k)   // k 번 비트 켜기 (k 추가)
mask & ~(1 << k)   // k 번 비트 끄기 (k 제거)
mask &  (1 << k)   // k 번 비트 켜져 있는지 체크
__builtin_popcount(mask)  // 켜진 비트 개수 (C++/GCC)

TSP (외판원 순회) 예시:

dp[mask][i] = "mask 에 속한 도시들을 방문했고, 현재 도시 i 에 있을 때의 최소 비용"

초기: dp[1 << start][start] = 0
전이: dp[mask][i] = min(dp[prev_mask][j] + dist[j][i])
      prev_mask = mask & ~(1 << i)  (i 없는 상태)
      j ∈ prev_mask, i ∉ prev_mask

답: dp[(1 << N) - 1][end] (모든 도시 방문, 도착지 end)

일반 패턴:

1. 각 원소 선택 여부를 비트 위치로
2. dp[mask] 또는 dp[mask][last] 형태
3. 전이는 비트 추가/제거로 표현
4. O(2^N × N) ~ O(2^N × N^2) 복잡도

알고리즘

TSP 문제 (도시 0 시작, 모든 도시 방문 후 0 복귀):

tsp(n, dist):
    dp = array[1 << n][n], fill with ∞
    dp[1][0] = 0   // 도시 0 하나만 방문, 현재 0

    for mask in 1..(1 << n):
        for i in 0..n-1:
            if !(mask & (1 << i)): continue
            prev_mask = mask ^ (1 << i)
            for j in 0..n-1:
                if !(prev_mask & (1 << j)): continue
                dp[mask][i] = min(dp[mask][i],
                                  dp[prev_mask][j] + dist[j][i])

    // 모든 도시 방문 후 0 으로
    full = (1 << n) - 1
    ans = ∞
    for i in 1..n-1:
        ans = min(ans, dp[full][i] + dist[i][0])

    return ans

구현

// TSP (외판원 순회), 도시 N 개, 0 시작 -> 모든 도시 -> 0
#include <bits/stdc++.h>
using namespace std;
​
const int INF = 1e9;
​
int main() {
  int n; cin >> n;
  vector<vector<int>> dist(n, vector<int>(n));
  for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
          cin >> dist[i][j];
​
  // dp[mask][i] = mask 방문, 현재 i 위치일 때 최소 비용
  vector<vector<int>> dp(1 << n, vector<int>(n, INF));
  dp[1][0] = 0;  // 도시 0 하나만 방문
​
  for (int mask = 1; mask < (1 << n); mask++) {
      for (int i = 0; i < n; i++) {
          if (!(mask & (1 << i))) continue;
          int prev = mask ^ (1 << i);
          for (int j = 0; j < n; j++) {
              if (!(prev & (1 << j))) continue;
              dp[mask][i] = min(dp[mask][i],
                                dp[prev][j] + dist[j][i]);
          }
      }
  }
​
  // 모든 도시 방문 후 0 복귀
  int full = (1 << n) - 1, ans = INF;
  for (int i = 1; i < n; i++)
      ans = min(ans, dp[full][i] + dist[i][0]);
​
  cout << ans << "\n";
}

# TSP (외판원 순회), Python 으로 비트마스크 DP
import sys
input = sys.stdin.readline
INF = int(1e9)
​
n = int(input())
dist = [list(map(int, input().split())) for _ in range(n)]
​
# dp[mask][i] = mask 방문, 현재 i 위치일 때 최소 비용
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0
​
for mask in range(1, 1 << n):
  for i in range(n):
      if not (mask & (1 << i)):
          continue
      prev = mask ^ (1 << i)
      for j in range(n):
          if not (prev & (1 << j)):
              continue
          dp[mask][i] = min(dp[mask][i],
                            dp[prev][j] + dist[j][i])
​
# 모든 도시 방문 후 0 복귀
full = (1 << n) - 1
ans = min(dp[full][i] + dist[i][0] for i in range(1, n))
print(ans)

// TSP (외판원 순회), Java 비트마스크 DP
import java.util.*;
import java.io.*;
​
public class Main {
  static final int INF = (int) 1e9;
​
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      int[][] dist = new int[n][n];
      for (int i = 0; i < n; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          for (int j = 0; j < n; j++)
              dist[i][j] = Integer.parseInt(st.nextToken());
      }
​
      // dp[mask][i] = mask 방문, 현재 i 위치일 때 최소 비용
      int[][] dp = new int[1 << n][n];
      for (int[] row : dp) Arrays.fill(row, INF);
      dp[1][0] = 0;
​
      for (int mask = 1; mask < (1 << n); mask++) {
          for (int i = 0; i < n; i++) {
              if ((mask & (1 << i)) == 0) continue;
              int prev = mask ^ (1 << i);
              for (int j = 0; j < n; j++) {
                  if ((prev & (1 << j)) == 0) continue;
                  dp[mask][i] = Math.min(dp[mask][i],
                                         dp[prev][j] + dist[j][i]);
              }
          }
      }
​
      int full = (1 << n) - 1, ans = INF;
      for (int i = 1; i < n; i++)
          ans = Math.min(ans, dp[full][i] + dist[i][0]);
​
      System.out.println(ans);
  }
}

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80

복잡도

N = 20 기준:

• 상태 개수: 2^20 × 20 ≈ 2.1 × 10^7
• 전이: O(N) 추가 → 총 O(2^N × N^2) ≈ 4 × 10^8, 1~2 초 내외

변형 / 활용

1. 해밀턴 경로 카운팅

dp[mask][i] = “mask 방문, i 에서 끝나는 경로 개수”.

2. 집합 분할 최소화

dp[mask] = “mask 에 속한 원소들을 여러 그룹으로 나누었을 때 최소 비용”. 전이: 부분집합 순회 sub ⊆ mask.

3. 조합 최적 배치

N 개 슬롯에 N 개 아이템 배치, dp[mask][slot] = 최적값.

4. Held-Karp 알고리즘 (TSP)

위 TSP 알고리즘의 정식 명칭. 1962 년 Held, Karp 가 동적 계획법으로 TSP 를 O(2^N × N^2) 로 해결.

함정

1. 비트 범위 초과

N = 20 이면 1 << 20 = 1,048,576. N = 30 이면 2^30 > 10^9, 배열 할당 불가능. N ≤ 20 엄수.

2. 비트 연산 실수

mask & (1 << k) 결과는 0 또는 2^k. 조건문은 if (mask & (1 << k)) 로, == 1 하면 안 됨.

3. 초기화 값

최소화 문제는 INF, 최대화 문제는 -INF, 카운팅은 0. 시작 상태만 적절히 설정.

4. 순회 순서

mask 를 오름차순 순회해야 prev_mask < mask 가 보장됨. DP 테이블은 작은 mask 부터 채워짐.

BOJ 연습 문제

참고

• 동적 계획법
• 완전 탐색
• 외판원 순회