비트마스크 DP는 언제 필요할까: 방문 상태를 정수 하나로 압축하는 방법

비트마스크 DP는 이름만 보고 판단하면 핵심을 놓치기 쉬운 주제입니다. 이 글은 최신 출처와 구조를 기준으로 독자가 실제로 확인해야 할 기준을 정리합니다.

핵심은 방문 상태를 비트로 압축해 DP 상태를 줄이는 방법 이해입니다. 단정적인 결론보다 확인 순서와 리스크를 분리해 보는 것이 중요합니다.

비트마스크 DP 흐름을 그림으로 보기

비트마스크 DP는 방문 배열을 숫자로 바꾸는 사고법이다

비트마스크 DP는 방문 여부처럼 참/거짓으로 표현되는 여러 상태를 정수 하나에 담는 방법입니다. 예를 들어 5개 도시 중 0, 2, 4번을 방문했다면 10101₂ 같은 숫자로 상태를 표현할 수 있습니다.

핵심은 방문한 집합 자체가 DP 상태가 되는 문제에서 비트마스크가 힘을 발휘한다는 점입니다.

왜 굳이 비트로 표현할까

방문 배열을 매번 복사하면 코드도 길고 상태 비교도 번거롭습니다. 비트마스크를 쓰면 특정 원소가 포함됐는지, 새 원소를 추가했는지, 전체를 방문했는지를 빠르게 계산할 수 있습니다.

bool visited = mask & (1 << i);      // i번을 방문했는가
int nextMask = mask | (1 << i);      // i번을 방문 상태에 추가
int fullMask = (1 << n) - 1;         // 모든 원소 방문

bool visited = mask & (1 << i);      // i번을 방문했는가
int nextMask = mask | (1 << i);      // i번을 방문 상태에 추가
int fullMask = (1 << n) - 1;         // 모든 원소 방문

쉬운 예시: 네 개 원소 중 고른 집합 표현하기

원소가 4개라면 방문 상태는 0000부터 1111까지 16개입니다. 0번과 2번을 골랐다면 mask는 0101₂입니다. 여기에 3번을 추가하면 1101₂가 됩니다.

원소: 0 1 2 3
mask 0101₂ = 0번, 2번 방문
3번 추가: 0101₂ | 1000₂ = 1101₂

원소: 0 1 2 3
mask 0101₂ = 0번, 2번 방문
3번 추가: 0101₂ | 1000₂ = 1101₂

이 작은 예시가 익숙해지면, dp[mask][last]에서 mask가 무엇을 뜻하는지 훨씬 덜 헷갈립니다.

현재 위치와 방문 상태를 함께 저장한다

많은 문제에서는 방문한 집합만으로는 부족합니다. 지금 어디에 있는지도 알아야 다음 비용을 계산할 수 있습니다. 그래서 dp[mask][last]처럼 방문 상태와 현재 위치를 함께 저장합니다.

const int INF = 1e9;
vector<vector> dp(1 << n, vector(n, INF));
dp[1][0] = 0;

for (int mask = 0; mask < (1 << n); mask++) {
    for (int last = 0; last < n; last++) {
        if (dp[mask][last] == INF) continue;
        for (int next = 0; next < n; next++) {
            if (mask & (1 << next)) continue;
            int nextMask = mask | (1 << next);
            dp[nextMask][next] = min(
                dp[nextMask][next],
                dp[mask][last] + cost[last][next]
            );
        }
    }
}

const int INF = 1e9;
vector<vector> dp(1 << n, vector(n, INF));
dp[1][0] = 0;

for (int mask = 0; mask < (1 << n); mask++) {
    for (int last = 0; last < n; last++) {
        if (dp[mask][last] == INF) continue;
        for (int next = 0; next < n; next++) {
            if (mask & (1 << next)) continue;
            int nextMask = mask | (1 << next);
            dp[nextMask][next] = min(
                dp[nextMask][next],
                dp[mask][last] + cost[last][next]
            );
        }
    }
}

입력 크기 제한을 먼저 봐야 한다

비트마스크 DP는 강력하지만 상태 수가 2^n입니다. n이 20이면 약 100만 상태라 경우에 따라 가능하지만, n이 30만 되어도 현실적으로 어렵습니다.

그래서 문제를 읽을 때 n이 작고, 방문한 집합이나 선택한 부분집합이 상태에 직접 들어간다면 비트마스크 DP를 의심해볼 수 있습니다.

어려운 예시: 열쇠와 문이 있는 격자 문제

비트마스크 DP는 외판원 문제뿐 아니라 격자 BFS와 섞이기도 합니다. 예를 들어 열쇠 a, b, c를 주워야 문 A, B, C를 통과할 수 있는 문제라면, 위치만으로는 상태가 부족합니다. 같은 칸에 있어도 어떤 열쇠를 갖고 있는지에 따라 갈 수 있는 길이 달라집니다.

상태 = (row, col, keyMask)

keyMask 001₂: a 열쇠만 있음
keyMask 011₂: a, b 열쇠 있음
같은 위치라도 keyMask가 다르면 다른 상태로 본다.

상태 = (row, col, keyMask)

keyMask 001₂: a 열쇠만 있음
keyMask 011₂: a, b 열쇠 있음
같은 위치라도 keyMask가 다르면 다른 상태로 본다.

이런 문제에서는 visited[row][col]만 쓰면 오답이 됩니다. visited[row][col][keyMask]처럼 방문 상태까지 포함해야 합니다.

언제 떠올리면 좋을까

1. n이 20 안팎으로 작다
2. 방문한 원소 집합이 중요하다
3. 부분집합을 모두 고려해야 한다
4. 현재 위치와 방문 상태를 함께 알아야 한다
5. 백트래킹은 가능한데 중복 상태가 많이 생긴다

정리

비트마스크 DP는 어려운 문법이 아니라 상태 표현 방식입니다. 방문 여부 배열을 정수 하나로 압축하면, 부분집합과 현재 위치를 기준으로 중복 계산을 줄일 수 있습니다. 대신 2^n이라는 한계가 분명하므로 입력 크기를 가장 먼저 확인해야 합니다.

관련 글로는 DP 점화식은 어떻게 세워야 할까, DP에서 메모이제이션과 테이블 방식은 무엇이 다를까, 백트래킹이란 무엇인가을 함께 보면 좋습니다. 외부 기준은 USACO Guide – Bitmask DP, CP-Algorithms – Bit manipulation, OI Wiki – State compression DP을 확인했습니다.