비트마스킹(Bitmasking) 외판원 순회 문제(TSP) 완벽해결

전 세계를 돌아다니며 물건을 파는 외판원(Traveling Salesman)이 있습니다. 이 외판원이 "자신의 집(시작 도시)에서 출발하여, 지도에 있는 모든 도시를 단 한 번씩만 빠짐없이 방문한 뒤, 다시 출발했던 원래 집으로 돌아오는 가장 짧고 저렴한 경로는 무엇일까?"라는 고전적인 수학적 딜레마. 이것이 바로 컴퓨터 과학에서 가장 유명한 NP-Hard 난제인 외판원 순회 문제(TSP, Traveling Salesman Problem)입니다. 도시가 10개만 넘어가도 모든 경로를 탐색하는 순열(Permutation) 방식은 O(N!)의 기하급수적인 시간이 걸려 슈퍼컴퓨터로도 풀기 힘들어집니다. 이 극악의 시간 복잡도를 O(N^2 * 2^N) 수준으로 끌어내려 코딩 테스트 통과가 가능하게 만들어 주는 기적의 조합이 바로 '동적 계획법(DP)'과 '비트마스킹(Bitmasking)'의 결합입니다. 오늘 이 글에서는 TSP 문제의 상태 정의부터 마법 같은 점화식 도출까지 낱낱이 파헤쳐 보겠습니다.

1. 브루트 포스(O(N!))의 붕괴와 DP의 도입

도시가 16개(N=16)라고 가정해 보겠습니다. 무식하게 모든 경로를 다 가보는 DFS 탐색은 $16!$(약 20조 번)의 연산을 요구하여 1초 안에 절대 해결할 수 없습니다. 우리는 여기서 한 가지 깨달음을 얻어야 합니다.
"1 $\rightarrow$ 2 $\rightarrow$ 3 $\rightarrow$ 4 로 이동한 상태에서 남은 도시를 도는 최소 비용이나, 1 $\rightarrow$ 3 $\rightarrow$ 2 $\rightarrow$ 4 로 이동한 상태에서 남은 도시를 도는 최소 비용은 완벽하게 똑같다!"
순서가 어떻든 간에 '현재 내가 서 있는 도시가 4번'이고, '방문한 도시의 종류가 {1, 2, 3, 4}'라면, 앞으로 남은 여정의 최솟값은 완전히 동일합니다. 이 중복된 연산을 막기 위해 우리는 DP(메모이제이션)를 도입해야 합니다.

2. 2차원 DP와 비트마스킹을 활용한 상태(State) 압축

DP 배열을 만들기 위해서는 '현재의 상태'를 인덱스로 표현해야 합니다. 우리는 두 가지 정보가 필요합니다.
1. 현재 내가 서 있는 도시의 번호 (current_city)
2. 지금까지 내가 방문한 도시들의 집합 (visited)

2-1. 비트마스킹을 통한 방문 기록 압축

16개의 도시를 방문했는지 체크하기 위해 크기 16짜리 불리언(Boolean) 배열을 DP의 인덱스로 쓸 수는 없습니다. 여기서 비트마스킹이 구세주로 등장합니다. 0번과 2번, 3번 도시를 방문했다면 이를 이진수 1101(2)로 표현하고, 십진수 정수 13 하나로 완벽하게 압축합니다.
이제 우리의 거대한 DP 테이블은 단 2차원 배열인 dp[current_city][visited_mask] 형태로 깔끔하게 정의됩니다. "현재 current_city에 있고, 지금까지 visited_mask 만큼의 도시들을 방문했을 때, 앞으로 남은 모든 도시를 다 돌고 무사히 집으로 돌아가는 데 드는 최소 비용"을 저장하는 것입니다.

3. TSP 마법의 점화식과 기저 조건(Base Case)

재귀 함수 dfs(int current, int visited)를 설계해 봅시다.

3-1. 기저 조건: 모든 도시를 다 방문했을 때

가장 밑바닥, 즉 모든 도시를 다 방문한 순간은 비트마스킹으로 어떻게 표현할까요? N이 4라면, 1111(2) 즉 (1 << N) - 1이 될 때가 완벽한 방문 상태입니다. 이때는 현재 도시에서 맨 처음 출발했던 0번 도시로 곧바로 돌아가는 길(간선)이 존재하는지 확인하고, 길이 있다면 그 비용을 반환(Return)하며 여행을 종료합니다.

3-2. 점화식: 다음 방문할 도시 찾기


// TSP 점화식 코어 로직 (Java 예시)
// 방문하지 않은 도시 i를 찾아 재귀적으로 파고듦
for (int i = 0; i < N; i++) {
    // 1. i번 도시를 이미 방문했는가? (AND 연산 활용)
    if ((visited & (1 << i)) != 0) continue; 
    
    // 2. 현재 도시에서 i번 도시로 가는 길이 없는가?
    if (cost[current][i] == 0) continue;

    // 3. 점화식 갱신: Min(현재 기록, i로 가는 비용 + i에서 남은 도시를 모두 도는 최소 비용)
    dp[current][visited] = Math.min(dp[current][visited], 
        cost[current][i] + dfs(i, visited | (1 << i))); // OR 연산으로 방문 처리
}

이 코드는 아직 안 간 도시 i를 찾아서, 현재 도시에서 i로 가는 톨게이트 비용과, i에 도착한 후 남은 도시를 다 돌고 집에 가는 비용(재귀 호출)을 합산하여 그중 가장 저렴한 루트를 현재 dp 맵에 캐싱(Caching)해 둡니다. 이 과정을 거치면 끔찍했던 계승(Factorial) 시간 복잡도가 DP 배열의 크기와 동일한 $O(N^2 \times 2^N)$으로 극적으로 최적화되며 코딩 테스트의 시간 제한을 여유롭게 통과하게 됩니다.

[핵심 요약]
1. 외판원 순회 문제(TSP)는 한 점에서 출발해 모든 노드를 한 번씩만 방문하고 돌아오는 최소 비용 경로를 찾는 NP-Hard 알고리즘입니다.
2. 중복 연산을 막기 위해 동적 계획법(DP)을 사용하며, 배열 인덱스에 방문 기록을 통째로 넣기 위해 이진수를 활용하는 비트마스킹(Bitmasking) 기법이 필수적으로 결합됩니다.
3. 상태를 dp[현재 도시][방문 비트]로 정의하고, 미방문 도시를 탐색하며 cost + dfs() 점화식을 통해 최솟값을 갱신하여 $O(N^2 \times 2^N)$의 최적화된 속도를 도출합니다.

코드 아카이브