[C++로 배우는 알고리즘과 자료구조 심화] Day 17: 비트마스크 동적 계획법 (Bitmask DP)

비트마스크 동적 계획법 (Bitmask DP)

비트마스크 동적 계획법은 상태를 이진수로 표현하여 여러 상태를 효율적으로 관리하는 기법입니다. 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 상태를 이진수로 표현하면 각 비트가 특정 원소의 포함 여부를 나타내어 간결하게 표현할 수 있습니다.

문제 예시: 외판원 문제 (Traveling Salesman Problem, TSP)

외판원 문제는 주어진 도시들을 방문하여 모든 도시를 한 번씩 방문하고 시작점으로 돌아올 때, 이동 비용의 합이 최소가 되도록 하는 경로를 찾는 문제입니다. 비트마스크 DP를 사용하여 해결할 수 있습니다.

문제 정의

• 주어진 도시 수 (n)
• 각 도시 간의 거리 (dist[i][j])
• 최소 이동 비용을 계산하여 출력

비트마스크 DP 구현

다음은 C++로 비트마스크 DP를 사용하여 외판원 문제를 해결하는 예제입니다.

#include <iostream>
#include <vector>
#include <climits>

// 최대 도시 수
const int MAX_N = 20;

// 거리 행렬
int dist[MAX_N][MAX_N];

// DP 테이블
int dp[1 << MAX_N][MAX_N];

// 도시 수
int n;

// 외판원 문제 해결 함수
int tsp(int mask, int pos) {
    if (mask == (1 << n) - 1) {
        return dist[pos][0];
    }

    if (dp[mask][pos] != -1) {
        return dp[mask][pos];
    }

    int answer = INT_MAX;

    for (int city = 0; city < n; ++city) {
        if ((mask & (1 << city)) == 0) {
            int newAnswer = dist[pos][city] + tsp(mask | (1 << city), city);
            answer = std::min(answer, newAnswer);
        }
    }

    return dp[mask][pos] = answer;
}

int main() {
    // 도시 수 입력
    std::cout << "도시 수를 입력하세요: ";
    std::cin >> n;

    // 거리 행렬 입력
    std::cout << "도시 간의 거리를 입력하세요:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> dist[i][j];
        }
    }

    // DP 테이블 초기화
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = -1;
        }
    }

    int result = tsp(1, 0);

    std::cout << "최소 이동 비용: " << result << std::endl;

    return 0;
}

설명

1. 입력:
   • n: 도시 수
   • dist: 도시 간의 거리 행렬
2. 비트마스크 DP 테이블:
   • dp[mask][pos]는 mask 상태에서 현재 pos 도시에 위치했을 때의 최소 이동 비용을 의미합니다.
   • 초기값으로 -1을 설정하여 아직 계산되지 않은 상태를 표시합니다.
3. 비트마스크와 재귀 함수:
   • mask는 현재 방문한 도시들을 이진수로 나타낸 것입니다. 예를 들어, mask = 5 (0101)은 도시 0과 2를 방문했음을 나타냅니다.
   • pos는 현재 위치한 도시입니다.
   • 모든 도시를 방문한 상태 (mask == (1 << n) - 1)에서 시작 도시로 돌아가는 비용을 반환합니다.
   • 이미 계산된 상태는 DP 테이블을 참조하여 반환합니다.
   • 아직 방문하지 않은 도시를 방문하여 최소 비용을 계산합니다.

비트마스크 동적 계획법의 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 18: 트리 DP(Tree DP)"에 대해 학습하겠습니다.