비트마스크 DP: 집합 상태를 정수로 압축하는 기법

지난 글에서 구간 DP로 구간을 분할하는 패턴을 살펴봤습니다. 이번에는 비트마스크 DP(Bitmask DP)를 다룹니다. 원소 n개의 집합 상태를 n비트 정수 하나로 표현하면, 2^n 개의 부분집합을 DP 테이블의 인덱스로 사용할 수 있습니다. 집합 관련 DP에서 지수 공간을 현실적 범위(n ≤ 20 정도)로 줄이는 강력한 기법입니다.

비트마스크로 집합 표현하기

n개의 원소를 가진 집합을 n비트 정수로 표현합니다. 비트 i가 1이면 원소 i가 포함된 상태입니다.

# n=4, 도시 0~3
# mask = 0b0101 = 5 → 도시 0과 2가 방문된 상태

# 핵심 비트 연산
def is_visited(mask, i):       return (mask >> i) & 1        # 비트 i 확인
def visit(mask, i):            return mask | (1 << i)         # 비트 i 추가
def unvisit(mask, i):          return mask ^ (1 << i)         # 비트 i 제거
def all_visited(mask, n):      return mask == (1 << n) - 1    # 전체 방문 확인
def count_visited(mask):       return bin(mask).count('1')    # 방문 개수

# 집합 열거: 특정 비트 집합의 모든 부분집합 탐색
def enumerate_subsets(mask):
    sub = mask
    while sub > 0:
        yield sub
        sub = (sub - 1) & mask
    yield 0

비트마스크 DP 상태 표현

TSP: 외판원 문제 (Travelling Salesman Problem)

n개 도시를 모두 방문하고 출발 도시로 돌아오는 최단 경로를 구합니다.

dp[mask][i] = mask에 표시된 도시들을 방문하고 현재 도시 i에 있을 때의 최소 비용.

import math

def tsp(dist: list) -> int:
    n = len(dist)
    INF = float('inf')
    # dp[mask][i]: visited=mask, 현재=i일 때 최소 비용
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0   # 도시 0에서 출발, 도시 0만 방문

    for mask in range(1, 1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            if not (mask >> u) & 1:    # u가 mask에 없으면 skip
                continue
            for v in range(n):
                if (mask >> v) & 1:    # v 이미 방문
                    continue
                new_mask = mask | (1 << v)
                new_cost = dp[mask][u] + dist[u][v]
                if new_cost < dp[new_mask][v]:
                    dp[new_mask][v] = new_cost

    # 모든 도시 방문 후 시작(0)으로 귀환
    full = (1 << n) - 1
    return min(dp[full][i] + dist[i][0] for i in range(1, n)
               if dp[full][i] < INF)

# 예: 4개 도시 거리 행렬
dist = [
    [0, 10, 15, 20],
    [10,  0, 35, 25],
    [15, 35,  0, 30],
    [20, 25, 30,  0],
]
print(tsp(dist))  # 80 (0→1→3→2→0)

시간 O(2^n · n²), 공간 O(2^n · n). n=20이면 약 4억 번 연산으로 실용적입니다. 완전 탐색(O(n!))과 비교하면 n=20에서 10^8배 이상 빠릅니다.

작업 배분 최소 비용

n명의 직원에게 n개의 작업을 1:1 배정할 때 총 비용 최소화입니다.

dp[mask] = 완료된 작업 집합이 mask일 때의 최소 비용. 직원 번호는 popcount(mask) - 1입니다.

작업 배분 비트마스크 DP

def assign_tasks(cost: list) -> int:
    n = len(cost)
    dp = [float('inf')] * (1 << n)
    dp[0] = 0

    for mask in range(1, 1 << n):
        i = bin(mask).count('1') - 1   # 현재 배정할 직원 인덱스
        for j in range(n):             # 작업 j를 직원 i에게 배정
            if mask & (1 << j):        # j가 mask에 포함(배정 예정)
                prev = mask ^ (1 << j)
                if dp[prev] + cost[i][j] < dp[mask]:
                    dp[mask] = dp[prev] + cost[i][j]

    return dp[(1 << n) - 1]

cost = [
    [9, 2, 7],
    [6, 4, 3],
    [5, 8, 1],
]
print(assign_tasks(cost))  # 7 (직원0→작업1:2, 직원1→작업2:3, 직원2→작업0:5? → 10)
# 실제 최적: 0→1(2) + 1→2(3) + 2→0(5) = 10? 또는 다른 조합

비트마스크 DP 적용 가능 조건

집합 상태가 DP의 차원 역할: n ≤ 20 (2^20 ≈ 10^6 상태)
순서나 포함 여부가 핵심: 방문 여부, 선택 여부
부분 집합 간 전이: 작은 집합 → 큰 집합으로 전이

# 집합 커버링: 원소 전체를 덮는 최소 집합 수
def set_cover(universe: int, sets: list) -> int:
    n = len(sets)
    dp = [float('inf')] * (1 << universe)
    dp[0] = 0

    for mask in range(1 << universe):
        if dp[mask] == float('inf'):
            continue
        for s in sets:
            dp[mask | s] = min(dp[mask | s], dp[mask] + 1)

    return dp[(1 << universe) - 1]

비트마스크 DP는 NP-hard 문제(TSP, 집합 커버, 해밀턴 경로 등)를 지수 시간에서 실용적인 의사다항 시간으로 낮춰주는 강력한 도구입니다.

지난 글: 구간 DP

다음 글: 트리 DP (Tree DP)

읽어주셔서 감사합니다. 😊