[알고리즘 Deep Dive #7] 외판원 순회 문제(TSP): 완전탐색에서 비트마스크 DP까지

들어가며

여러 도시를 한 번씩 방문하고 다시 출발점으로 돌아오는 가장 짧은 경로를 찾는 문제.
이 단순해 보이는 문제는 알고리즘 세계에서 가장 유명한 난제 중 하나인 외판원 순회 문제(Traveling Salesman Problem, TSP)이다.

TSP는 단순한 경로 탐색 문제가 아니다.
도시의 개수가 조금만 늘어나도 가능한 경로 수는 폭발적으로 증가하며, 이는 곧 조합 폭발(combinatorial explosion)로 이어진다.

예를 들어 도시가 N개라면 가능한 경로는 다음과 같다:

• 시작 도시를 고정해도:
  (N-1)!

즉,

• N = 10 → 약 36만
• N = 15 → 약 8.7조

이처럼 완전탐색은 매우 빠르게 현실적으로 불가능한 수준에 도달한다.

---

이 문제는 다음과 같은 이유로 특히 중요하다:

• NP-hard 문제의 대표 사례
• 그래프 + DP + 비트마스크가 결합된 핵심 문제
• 다양한 최적화 문제(물류, 회로 설계, DNA 분석 등)의 기반

---

이번 글에서는 다음 흐름으로 TSP를 깊이 있게 파헤친다:

1. 완전탐색 (Brute Force)
2. 가지치기 (Backtracking)
3. 동적 계획법 (DP)
4. 비트마스크 DP (Held-Karp)

그리고 최종적으로,
O(N^2 × 2^N)으로 해결하는 핵심 기법까지 도달하는 것이 목표다.

---

완전탐색으로 시작하기: 왜 TSP는 어려운가?

TSP를 처음 보면 자연스럽게 이렇게 생각하게 된다.

👉 “모든 경로를 다 확인하면 되지 않을까?”

즉, 가능한 모든 순열을 만들어서
각 경로의 비용을 계산하고 최솟값을 찾는 방식이다.

---

하지만 이 접근은 거의 바로 한계에 부딪힌다.

도시가 N개일 때 가능한 경로 수는:

• (N-1)!

즉,

• N = 10 → 약 36만 (가능)
• N = 12 → 수천만 (이미 느림)
• N = 15 → 수조 단위 (불가능)

---

👉 결론:

완전탐색은 TSP를 해결하기에는 너무 느리다.

---

그렇다면 여기서 중요한 질문이 생긴다.

👉 “왜 이렇게 느린 걸까?”

핵심 원인은 하나다.

👉 같은 경로를 계속 다시 계산하고 있기 때문

예를 들어,

• 0 → A → B
• 0 → A → C

이 두 경우는 모두
0 → A까지의 계산을 공유하지만,
완전탐색에서는 이를 매번 다시 계산한다.

---

이 문제를 해결하기 위한 방향은 명확하다.

👉 “이미 계산한 결과를 재사용하자”

가지치기(Backtracking): 완전탐색을 줄일 수 있을까?

완전탐색이 너무 느리다는 건 분명하다.
그렇다면 탐색 자체를 줄일 수는 없을까?

여기서 등장하는 것이 가지치기(Backtracking)이다.

---

핵심 아이디어

탐색 도중에 다음과 같은 상황이 나오면:

• 이미 현재까지의 비용이 최소값보다 커진 경우

더 이상 진행할 필요 없이 중단한다.

---

직관적인 예시

경로를 탐색하다가:

• 현재 비용: 100
• 이미 찾은 최적 경로: 80

이 상태라면
이 이후 경로는 아무리 좋아도 80보다 작아질 수 없다.

즉시 탐색을 멈춘다.

---

효과

• 평균적으로 탐색 공간을 줄일 수 있음
• 하지만 최악의 경우 여전히 모든 경로를 확인해야 함

시간 복잡도는 여전히 O(N!)

---

한계

Backtracking은 “덜 탐색”하게 해줄 뿐,
문제의 본질적인 복잡도를 바꾸지는 못한다.

즉,

• 운이 좋으면 빠름
• 운이 나쁘면 여전히 매우 느림

---

결국 더 근본적인 해결이 필요하다.

동적 계획법(DP): 중복 계산을 없애기

앞에서 본 것처럼, 완전탐색과 가지치기는 결국 같은 문제를 반복해서 계산한다는 한계를 벗어나지 못한다.

그렇다면 방향을 조금 바꿔보자.

“모든 경로를 다 보자”가 아니라,
“이미 계산한 결과를 다시 쓰자”로 접근하는 것이다.

이게 바로 동적 계획법(DP)의 핵심이다.

---

어떤 부분이 중복될까?

TSP를 다시 보면, 경로는 이런 식으로 만들어진다.

• 0 → A → B → C
• 0 → A → C → B

이 두 경로는 시작부터 A까지의 과정이 완전히 같다.

하지만 완전탐색에서는 이걸 매번 새로 계산한다.

---

상태를 정의해보자

중복을 제거하려면, 문제를 “상태”로 나눠야 한다.

TSP에서는 이렇게 정의할 수 있다:

• 현재 위치 (현재 도시)
• 지금까지 방문한 도시들의 집합

즉,

“현재 도시가 i이고, 지금까지 방문한 도시가 S일 때의 최소 비용”

이 값을 저장해두고 재사용하는 것이다.

---

왜 ‘집합’이 중요할까?

단순히 “어디에 있는가”만으로는 부족하다.

예를 들어 같은 도시 A에 있더라도,

• 어떤 경우는 B, C를 이미 방문했고
• 어떤 경우는 아직 방문하지 않았을 수도 있다

이 두 상황은 완전히 다른 문제다.

그래서 반드시
“어디까지 방문했는가”를 함께 상태로 가져가야 한다.

---

DP의 핵심 구조

이제 문제는 이렇게 바뀐다:

• 작은 문제: 일부 도시만 방문한 상태
• 큰 문제: 모든 도시를 방문한 상태

그리고

• 작은 문제의 답을 이용해
• 큰 문제를 해결한다

---

이 방식으로 접근하면
중복 계산이 사라지면서 성능이 크게 개선된다.

하지만 아직 한 가지 문제가 남아 있다.

“방문한 도시들의 집합”을 어떻게 효율적으로 표현할까?

다음 섹션에서는
이 문제를 해결하는 핵심 기술인
비트마스크(Bitmask)를 살펴본다.

---

비트마스크(Bitmask): 집합을 효율적으로 표현하기

앞에서 DP를 설계하면서
“방문한 도시들의 집합”이 필요하다는 걸 확인했다.

그런데 여기서 바로 문제가 생긴다.

집합을 그대로 사용하면:

• 비교가 느리고
• 저장도 비효율적이며
• DP 상태 관리가 어려워진다

---

해결 방법: 비트마스크

집합을 정수 하나로 표현하는 방법이 있다.
바로 비트마스크(Bitmask)다.

각 도시를 하나의 비트에 대응시키는 방식이다.

---

예시

도시가 4개라면:

• 0번 도시 → 0001
• 1번 도시 → 0010
• 2번 도시 → 0100
• 3번 도시 → 1000

---

방문 상태 표현

예를 들어,

• 0번, 2번 도시를 방문했다면

0101 (2진수) = 5 (10진수)

이 숫자 하나로 “방문 집합”을 표현할 수 있다.

---

왜 좋은가?

비트마스크를 사용하면 다음이 매우 빨라진다.

• 도시 방문 여부 확인 → O(1)
• 도시 추가 → O(1)
• 상태 비교 → O(1)

즉,
DP에서 요구하는 “상태 관리”가 매우 효율적으로 바뀐다.

---

자주 사용하는 연산

# i번 도시 방문 여부 확인
if mask & (1 << i):

# i번 도시 방문 처리
mask | (1 << i)

# i번 도시 방문 해제
mask & ~(1 << i)

이제 상태가 완성됐다

이제 우리는 TSP를 다음과 같이 정의할 수 있다.

• dp[mask][i]

의미:

“mask에 포함된 도시들을 모두 방문했고, 현재 i번 도시에 있을 때의 최소 비용”

---

비트마스크 DP (Held-Karp): TSP를 현실적으로 푸는 방법

이제 필요한 재료는 모두 준비됐다.

• 상태 정의: dp[mask][i]
• 집합 표현: 비트마스크

이걸 바탕으로 TSP를 효율적으로 해결하는
비트마스크 DP (Held-Karp 알고리즘)를 완성해보자.

---

상태 정의

dp[mask][i]

의미:

• mask: 지금까지 방문한 도시들의 집합
• i: 현재 위치한 도시

즉,

mask에 포함된 도시들을 모두 방문하고, i에 도착했을 때의 최소 비용이다.

---

점화식

현재 상태에 도달하기 직전에는,
어떤 도시 j에서 현재 도시 i로 이동했을 것이다.

그래서 점화식은 다음처럼 세울 수 있다.

dp[mask][i] = min(
    dp[mask ^ (1 << i)][j] + graph[j][i]
)

단,

• j는 mask에 포함되어 있어야 하고
• j != i 여야 한다.

---

초기값

출발 도시를 0번이라고 하면 시작 상태는 다음과 같다.

dp[1 << 0][0] = 0

즉,
0번 도시만 방문한 상태에서 시작 비용은 0이다.

---

최종 답

모든 도시를 방문한 뒤에는 다시 출발점으로 돌아와야 한다.

min(dp[(1 << n) - 1][i] + graph[i][0])

---

구현 (Python)

import sys
input = sys.stdin.readline

n = int(input())
INF = int(1e9)
dp = [[-1] * (1 << n) for _ in range(n)]

graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

def dfs(s, visited):
  if visited == (1 << n) - 1: # 1...1111 (모든 노드를 방문했다면)
    if graph[s][0] == 0: # 출발점으로 가는 경로가 없을 때
        return INF
    else: # 시작점으로 돌아가는 비용 반환 (종료조건 == 바닥)
        return graph[s][0]

  if dp[s][visited] != -1: # 이미 계산했다면 메모 사용
    return dp[s][visited]

  dp[s][visited] = INF
  # 계산하지 않았다면 계산하기 (재귀 호출)
  for i in range(n):
    if not (visited & (1 << i)) and graph[s][i] != 0: # i번째 노드를 방문하지 않았다면 
      dp[s][visited] = min(dp[s][visited], graph[s][i] + dfs(i, visited | (1 << i)))
    
  return dp[s][visited]

# dfs(s, 1) 의미 : s에서 시작해서 0번 노드만 방문했고, 나머지 노드들은 방문하지 않았다.
print(dfs(0, 1))

---

시간 복잡도

상태 수는 대략 2^N × N개이고,
각 상태에서 다음 도시를 확인하는 데 N이 걸린다.

따라서 전체 시간 복잡도는 다음과 같다.

O(N^2 × 2^N)

---

왜 이게 의미 있을까?

완전탐색의 O(N!)와 비교하면 여전히 큰 수이긴 하다.
하지만 접근 가능한 입력 크기가 완전히 달라진다.

즉,
무작정 모든 경로를 보는 것이 아니라
중복되는 상태를 한 번만 계산하는 방식으로 바뀐 것이다.

이 차이 때문에 TSP는 비로소 “풀 수 있는 문제”가 된다.

마무리: TSP에서 배우는 문제 해결의 핵심

이번 글에서는 외판원 순회 문제(TSP)를 통해
단순한 탐색에서 시작해 점점 더 효율적인 방법으로 발전하는 과정을 살펴봤다.

흐름을 정리하면 다음과 같다.

• 완전탐색 → 너무 느림
• 가지치기 → 조금 나아지지만 근본 해결은 아님
• DP → 중복 계산 제거
• 비트마스크 DP → 상태를 효율적으로 표현

---

이 문제의 진짜 포인트

TSP에서 가장 중요한 건 구현이 아니다.

핵심은 이 한 가지다.

“문제를 어떻게 상태로 정의할 것인가”

• 단순히 위치만 보면 부족하고
• “어디까지 방문했는지”까지 포함해야 한다

이 관점을 떠올리는 순간,
문제는 비로소 풀리기 시작한다.

---

언제 이 기법을 떠올려야 할까?

다음과 같은 특징이 보이면
비트마스크 DP를 의심해볼 수 있다.

• 방문 여부가 중요한 문제
• 순서가 결과에 영향을 주는 문제
• N이 작고 (대략 15~20)
• 모든 경우를 탐색해야 하는 문제

---

한 줄 정리

TSP는 단순한 그래프 문제가 아니라,

“상태 설계 + DP + 비트마스크”가 결합된 종합 문제다.