비트마스크 DP

방문 집합을 비트로 든 채 상태를 전이한다 — 외판원 문제.

골드 II

1강 방문 집합을 비트로 든 DP 공식

어떤 문제를 푸는가

"어떤 원소들을 이미 사용했는가" 같은 부분집합 상태 가 DP의 차원이 되어야
할 때, 그 집합을 정수의 비트로 압축해 상태로 삼는 기법입니다. 원소 수가 작을
때( $n \le 20$ 정도)만 가능하며, 대표 문제가 외판원 문제(TSP) 입니다.

외판원 문제로 보는 핵심

$$n$$ 개 도시를 모두 한 번씩 방문하고 출발 도시로 돌아오는 최소 비용 순회 를
구합니다. 단순 완전 탐색은 $$O(n!)$$ 이라 $$n=12$$ 만 돼도 불가능합니다.

상태를 이렇게 둡니다.

$dp[mask][i] = \text{집합 } mask \text{의 도시를 모두 방문했고 현재 } i \text{에 있을 때 최소 비용}$

mask의 $$i$$ 번째 비트는 켜져 있어야 합니다(지금 $$i$$ 에 있으니 $$i$$ 는 방문됨).

점화식

$$i$$ 에 도달하기 직전 정점 $$j$$ 에서 왔다고 보면,

$dp[mask][i] = \min_{j \in mask,\ j \ne i} \bigl( dp[mask \setminus \{i\}][j] + cost[j][i] \bigr)$

" $$i$$ 를 빼낸 집합을 $$j$$ 까지 방문하고, $j \to i$ 로 이동"한 비용입니다.
기저는 출발 도시 $$s$$ 만 방문한 상태 $dp[\{s\}][s] = 0$ . 답은 모든 도시를
방문한 뒤 출발지로 돌아오는 비용

$\min_{i} dp[(1{\ll}n) - 1][i] + cost[i][s]$

왜 옳은가

순회의 마지막 두 정점만 보면, " $$i$$ 로 끝나는 부분 경로의 최소 비용"은 그 직전
정점 $$j$$ 를 무엇으로 골랐는지에만 의존하고, 어떤 순서로 $$mask$$ 를 방문했는지는
무관 합니다. 같은 (방문 집합, 현재 위치)면 미래 비용이 동일하므로, 이
요약이 충분한 상태가 됩니다. 이것이 $$n!$$ 을 $2^n \cdot n$ 으로 압축하는 근거입니다.

복잡도

상태 수 $2^n \cdot n$ , 각 전이 $$O(n)$$ 이므로

$O(2^n \cdot n^2)$

$$n = 16$$ 이면 약 $1.7 \times 10^7$ 로 충분, $$n = 20$$ 이면 $4 \times 10^8$ 로
빡빡합니다. $$n$$ 이 20을 넘으면 비트마스크 DP는 보통 무리 입니다.

어떤 문제가 이 형태인가

"모든 것을 한 번씩" + "작은 원소 수" → 방문 집합을 마스크로.
"짝짓기/배정" + "작은 한쪽 크기" → 한쪽의 사용 집합을 마스크로.
격자 채우기에서 "한 줄의 칸 사용 패턴"을 마스크로(브로큰 프로파일).

다음 강의에서 TSP 구현과 메모리/순회 디테일을 봅니다.

2강 비트마스크 DP 구현과 패턴 공식

TSP 구현 (C++, 반복문 채우기)

mask를 오름차순으로 돌면 부분집합이 항상 먼저 계산됩니다(작은 mask가 작은 수).

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;

int main() {
    int n; cin >> n;
    vector<vector<long long>> cost(n, vector<long long>(n));
    for (auto& row : cost) for (auto& x : row) cin >> x;

    int FULL = (1 << n) - 1;
    vector<vector<long long>> dp(1 << n, vector<long long>(n, INF));
    dp[1][0] = 0;                         // 도시 0에서 출발, {0}만 방문

    for (int mask = 1; mask <= FULL; mask++) {
        for (int i = 0; i < n; i++) {
            if (dp[mask][i] == INF) continue;
            if (!(mask & (1 << i))) continue;
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue;    // 이미 방문한 곳은 건너뜀
                int nmask = mask | (1 << j);
                long long nd = dp[mask][i] + cost[i][j];
                dp[nmask][j] = min(dp[nmask][j], nd);
            }
        }
    }

    long long ans = INF;
    for (int i = 0; i < n; i++)
        if (cost[i][0] > 0 || i == 0)
            ans = min(ans, dp[FULL][i] + cost[i][0]);  // 출발지로 복귀
    cout << ans << '\n';
}

여기서는 "다음 도시 $$j$$ 로 전진"하는 forward 갱신을 썼습니다. 출발지 복귀가
불가능한 간선(비용 0/없음) 처리는 문제 정의에 맞춰 조정하세요.

메모이제이션(재귀) 형태

long long dp[1 << 16][16];   // 미리 -1로 채움
long long solve(int mask, int i) {
    if (mask == FULL) return cost[i][0];
    long long& res = dp[mask][i];
    if (res != -1) return res;
    res = INF;
    for (int j = 0; j < n; j++)
        if (!(mask & (1 << j)))
            res = min(res, cost[i][j] + solve(mask | (1 << j), j));
    return res;
}
// 호출: solve(1, 0)

흔한 함정

1 << i 오버플로 — $$n$$ 이 31 이상은 비트마스크 DP 대상이 아니지만,
실수로 1 << n을 int로 다루다 음수가 되지 않게 주의.
순회 순서 — 반복 구현에서 mask를 오름차순으로 돌아야 부분집합이 먼저
계산됩니다. 내림차순이면 틀립니다.
메모리 — dp[1<<n][n]가 $2^{20} \cdot 20 \cdot 8$ 바이트면 약 160MB로
위험. long long 대신 int나 1차원 평탄화로 줄이기.
시작/복귀 조건 — TSP에서 출발지 복귀를 답에 포함하는지 정확히.

응용 패턴

외판원 / 최소 해밀턴 경로 — 위 골격.
배정 문제(작은 N) — 사람 $$i$$ 에게 일 $$j$$ 배정, 사용한 일 집합을 마스크로.
$$dp[mask]$$ = 켜진 비트 수만큼 사람을 배정했을 때 최소 비용.
집합 분할 / 커버 — "이 부분집합을 한 그룹으로" 결정, 부분집합 순회( $$3^n$$ ).
브로큰 프로파일 DP — 격자 타일링에서 경계 한 줄의 상태를 마스크로.

핵심은 늘 같습니다. 작은 원소 집합 + "무엇을 썼는가"가 상태 이면 비트마스크
DP를 떠올리고, $$2^n$$ 규모가 시간·메모리에 들어맞는지부터 점검하세요.

3강 실전 가이드 — N≤20 배정·순회 문제의 정석 공식

출제 신호

$N \le 16{\sim}20$ + "모든 ○○를 한 번씩 방문/배정/사용" — 이 조합이
보이면 $O(2^N \cdot N)$ 또는 $O(2^N \cdot N^2)$ DP를 의심합니다.
외판원 순회(TSP), 일 배정, 학생-과목 매칭, 전구 끄기.
"순서는 마음대로지만 각각 정확히 한 번", "이미 처리한 것들의 집합만이
미래에 영향을 준다" — 순서 자체가 아니라 집합이 상태라는 신호입니다.
$$N!$$ 완전 탐색( $$N = 12$$ 에서 이미 $4.8 \times 10^8$ )이 막히고,
$$2^N$$ 은 되는 크기 — $$N = 20$$ 이면 $2^{20} \approx 10^6$ .

풀이 결정 절차

"지금까지 무엇을 했는가"가 집합 + (필요시) 마지막 원소로 요약되는지
확인합니다. TSP는 마지막 도시가 다음 비용에 영향을 주므로
dp[mask][last], 단순 배정은 dp[mask]로 충분합니다.
메모리 검산 — dp[1<<20][20]은 $2 \times 10^7$ 항목. int면 80MB로
위험할 수 있으니 자료형과 제한을 확인합니다.
시간 검산 — $2^N \times N^2$ ( $$N=20$$ 이면 $4 \times 10^8$ )은 경계선입니다.
전이를 $$O(N)$$ 으로 줄일 수 있는지 봅니다.
배정 문제의 표준 가지치기 — " $$i$$ 번째 사람은 popcount(mask)로 결정"되게
하면 상태에서 사람 차원이 사라집니다.

자주 하는 실수

마스크 순회 순서 — dp[mask]가 자신보다 작은 mask에서만 오도록
전이를 짜면, mask 오름차순 for 문으로 충분합니다. 반대로 "mask에서 비트를
켜며 전파(push)"하는 방식과 "켜진 비트를 보고 당겨오기(pull)"를 섞으면
덜 계산된 상태를 읽는 버그가 납니다. 한 방식으로 통일하세요.

// 배정 문제: i 번째 사람(= popcount) 에게 일 j 를 준다 — push 방식
vector<long long> dp(1 << n, INF);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
    if (dp[mask] == INF) continue;
    int i = __builtin_popcount(mask);     // 다음에 배정받을 사람
    if (i == n) continue;
    for (int j = 0; j < n; j++)
        if (!(mask & (1 << j)))
            dp[mask | (1 << j)] = min(dp[mask | (1 << j)],
                                      dp[mask] + cost[i][j]);
}

TSP에서 시작점 처리 — 순회는 회전 대칭이므로 시작 도시를 0번으로
고정해 dp[1][0] = 0에서 출발하면 상태가 $$1/N$$ 로 줄어듭니다. 모든
시작점을 다 돌리는 낭비가 흔합니다. 마지막에 dp[full][last] + cost[last][0]
의 최솟값, 그리고 돌아오는 간선이 없는 경우(INF) 제외를 잊지 마세요.
도달 불가 상태에서 전이 — dp[mask] == INF 스킵이 없으면 INF에 비용이
더해져 오버플로하거나 가짜 경로가 생깁니다.
1 << j의 32비트 한계와 popcount — $N \ge 31$ 은 1LL, 파이썬은
bin(mask).count('1') 반복 호출이 느리므로 popcount를 전이 밖에서 구합니다.
메모리 초과 — $2^{20} \times 20$ 짜리 2차원이 필요 없는 문제(dp[mask]로
충분)인데 습관적으로 last 차원을 붙이는 경우. 상태 설계를 먼저 적으세요.

연습 방법

사이드바 연습 목록에서 dp[mask] 단독으로 풀리는 배정 문제로 시작해,
dp[mask][last]가 필요한 외판원 순회로 올라가세요. 두 문제의 차이("마지막
원소가 미래 비용에 영향을 주는가")를 설명할 수 있으면 이 단원의 핵심을
잡은 것입니다. 같은 문제를 재귀+메모이제이션과 반복문 두 방식으로 짜 보는
것도 좋은 훈련입니다. 태그된 문제 3문제 이상 해결 시 마스터 처리되어
레이팅 CLASS 보너스에 반영됩니다.