외판원 순회 ⭐⭐⭐

Gold1

백준📅 2025-07-16

DP비트마스크메모이제이션

문제 설명

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오

제한사항

2 ≤ N ≤ 16
각 비용은 1,000,000 이하의 양의 정수
갈 수 없는 경우는 0이 주어진다
항상 순회할 수 있는 경우만 입력으로 주어진다

입출력 예

입력

출력

설명

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다.

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

풀이 접근법

시간복잡도 : O(2^n × n²)

공간복잡도 : O(2^n × n)

사용 알고리즘 :

DP비트마스크메모이제이션

핵심 포인트 :

비트마스크로 방문한 도시들의 집합을 표현
Top-Down DP로 부분 문제의 최적해 구하기
메모이제이션으로 중복 계산 방지
갈 수 없는 경로(cost=0) 처리 필요

경계값/반례 :

갈 수 없는 경로가 있는 경우: cost=0인 경로 제외
시작점으로 돌아갈 수 없는 경우: 도달할 수 없는 수 반환
Integer.MAX_VALUE 오버플로우: 안전한 큰 수 값 사용

핵심 아이디어

비트마스크 DP로 TSP 최적화 문제
상태 : [방문한 도시들의 집합, 현재 위치]
점화식 : dp[mask][current] = min(다른경우, dp[mask|next][next] + cost[current][next])
메모이제이션으로 중복 상태 계산 방지

해결 방법

dp[mask][current] = 현재 상태에서 TSP 완료까지의 최소 비용으로 상태 정의
모든 도시 방문 시 시작점으로 돌아가는 비용 반환
갈 수 없는 경로 제외 처리
메모이제이션 처리

내부 해부 과정

costs = [[0, 10, 15, 20], [5, 0, 9, 10], [6, 13, 0, 12], [8, 8, 9, 0]]

총 4개의 도시가 존재. 처음 시작을 0번 도시로 가정
0번 도시에서 시작이므로 0번을 방문
- 비트마스크 : 0001
- 현재 위치 : 0번
0번에서 갈 수 있는 도시들 = 1, 2, 3번
- 1번 도시로 가는 경우 (비용 : costs[0][1] = 10)
  - 비트마스크 : 0011
  - 현재 위치 : 1번
- 2번 도시로 가는 경우 (비용 : costs[0][2] = 15)
  - 비트마스크 : 0101
  - 현재 위치 : 2번
- 3번 도시로 가는 경우 (비용 : costs[0][3] = 20)
  - 비트마스크 : 1001
  - 현재 위치 : 3번
각 도시에서 다음 도시로 가는 경우
- 1번도시 (비용 = 10)
  - 0번 도시로 가는 경우 ⇒ 이미 지남
  - 2번 도시로 가는 경우 (비용 : costs[1][2] = 9)
    - 비트마스크 : 0111
    - 현재 위치 : 2번 (비용 = 19)
      - 0번 도시로 가는 경우 ⇒ 이미 지남
      - 1번 도시로 가는 경우 ⇒ 이미 지남
      - 3번 도시로 가는 경우 (비용 : costs[2][3] = 12)
        비트마스크 : 1111
        현재 위치 : 3번 (비용 = 31) ⇒ 다시 0번으로 최종 비용 = 39
  - 3번 도시로 가는 경우 (비용 : costs[1][3] = 10)
    - 비트마스크 : 1011
    - 현재 위치 : 3번 (비용 = 20)
      - 0번 도시로 가는 경우 ⇒ 이미 지남
      - 1번 도시로 가는 경우 ⇒ 이미 지남
      - 2번 도시로 가는 경우 (비용 : costs[3][2] = 9)
        비트마스크 : 1111
        현재 위치 : 2번 (비용 = 29) ⇒ 다시 0번으로 최종 비용 = 35
- 2번도시 (비용 = 15)
  - 0번 도시로 가는 경우 ⇒ 이미 지남
  - 1번 도시로 가는 경우 (비용 : costs[2][1] = 13)
    - 비트마스크 : 0111
    - 현재 위치 : 1번 (비용 = 28)
      - 0번 도시로 가는 경우 ⇒ 이미 지남
      - 2번 도시로 가는 경우 ⇒ 이미 지남
      - 3번 도시로 가는 경우 (비용 : costs[1][3] = 10)
        비트마스크 : 1111
        현재 위치 : 3번 (비용 = 38) ⇒ 다시 0번으로 최종 비용 = 46
  - 3번 도시로 가는 경우 (비용 : costs[2][3] = 12)
    - 비트마스크 : 1101
    - 현재 위치 : 3번 (비용 = 27)
      - 0번 도시로 가는 경우 ⇒ 이미 지남
      - 1번 도시로 가는 경우 (비용 : costs[3][1] = 8)
        비트마스크 : 1111
        현재 위치 : 1번 (비용 = 35) ⇒ 다시 0번으로 최종 비용 = 40
      - 2번 도시로 가는 경우 ⇒ 이미 지남
- 3번도시 (비용 = 20)
  - 0번 도시로 가는 경우 ⇒ 이미 지남
  - 1번 도시로 가는 경우 (비용 : costs[3][1] = 8)
    - 비트마스크 : 1011
    - 현재 위치 : 1번 (비용 = 28)
      - 0번 도시로 가는 경우 ⇒ 이미 지남
      - 2번 도시로 가는 경우 (비용 : costs[1][2] = 9)
        비트마스크 : 1111
        현재 위치 : 2번 (비용 = 37) ⇒ 다시 0번으로 최종 비용 = 43
      - 3번 도시로 가는 경우 ⇒ 이미 지남
  - 2번 도시로 가는 경우 (비용 : costs[3][2] = 9)
    - 비트마스크 : 1101
    - 현재 위치 : 2번 (비용 = 29)
      - 0번 도시로 가는 경우 ⇒ 이미 지남
      - 1번 도시로 가는 경우 (비용 : costs[2][1] = 13)
        비트마스크 : 1111
        현재 위치 : 1번 (비용 = 42) ⇒ 다시 0번으로 최종 비용 = 47
      - 3번 도시로 가는 경우 ⇒ 이미 지남
가장 최소의 비용은 35

생각 과정

비트마스크로 방문 관리 : 0001, 0011, 0101, 1001, 0111, 1011, 1101, 1111
- 비트마스크는 2의 4승인 16가지 경우로 표현 가능
  - 계산이 들어갔는지 여부를 파악하기 위해 모두 -1로 초기화
  - 다만, 채워지는 것은 0번 도시부터 시작하므로 경우의 수는 반으로 줄어든 8개만 나올 것이다.
- 비트마스크로 판단하는 것
  - 이미 방문한 도시인지
  - 모든 도시를 방문했는지
  - 메모이제이션된 것이 있는지 (같은 계산을 여러 번 하지 않기 위해)
현재 위치와 다음 위치가 확정되면 비용을 알 수 있다.
- costs[current][next]
다시 돌아오기 직전까지는 경우가 3가지다.
1. [mask, current] = [1111, 1]이 나오는 경우
  - 0 → 3 → 2 → 1
  - 0 → 2 → 3 → 1
2. [mask, current] = [1111, 2]이 나오는 경우
  - 0 → 3 → 1 → 2
  - 0 → 1 → 3 → 2
3. [mask, current] = [1111, 3]이 나오는 경우
  - 0 → 1 → 2 → 3
  - 0 → 2 → 1 → 3

실제 과정

costs = [[0, 10, 15, 20], [5, 0, 9, 10], [6, 13, 0, 12], [8, 8, 9, 0]]

dp([0001], 0)

for 반복문을 돈다. min = ∞
min = min(∞, dp([0011], 1) + costs[0][1]) = min(∞, 25 + 10) = 35
dp([0011], 1
- for 반복문을 돈다. min = ∞
- min = min(∞, dp([0111], 2) + costs[1][2]) = min(∞, 20 + 9) = 29
  dp([0111], 2)
  - for 반복문을 돈다. min = ∞
  - min = min(∞, dp([1111], 3) + costs[2][3]) = min(∞, 8 + 12) = 20
    dp([1111], 3) = costs[3][0] = 8
  - min = 20
- min = min(∞, dp([1011], 3) + costs[1][3]) = min(29, 15 + 10) = 25
  dp([1011], 3)
  - for 반복문을 돈다. min = ∞
  - min = min(∞, dp([1111], 2) + costs[3][2]) = min(∞, 6 + 9) = 15
    - dp([1111], 2) = costs[2][0] = 6
  - min = 15
- min = 25
min = min(∞, dp([0101], 2) + costs[0][2]) = min(35, 25 + 15) = 35
dp([0101], 2)
- for 반복문을 돈다. min = ∞
- min = min(∞, dp([0111], 1) + costs[2][1]) = min(∞, 18 + 13) = 31
  dp([0111], 1)
  - for 반복문을 돈다. min = ∞
  - min = min(∞, dp([1111], 3) + costs[1][3]) = min(∞, 8 + 10) = 18
    dp([1111], 3) = costs[3][0] = 8
  - min = 18
- min = min(∞, dp([1101], 3) + costs[2][3]) = min(31, 13 + 12) = 25
  dp([1101], 3)
  - for 반복문을 돈다. min = ∞
  - min = min(∞, dp([1111], 1) + costs[3][1]) = min(∞, 5 + 8) = 13
    dp([1111], 1) = costs[1][0] = 5
  - min = 13
- min = 25
min = min(∞, dp([1001], 3) + costs[0][3]) = min(35, 23 + 20) = 35
dp([1001], 3)
- for 반복문을 돈다. min = ∞
- min = min(∞, dp([1011], 1) + costs[3][1]) = min(∞, 15 + 8) = 23
  dp([1011], 1)
  - for 반복문을 돈다. min = ∞
  - min = min(∞, dp([1111], 2) + costs[1][2]) = min(∞, 6 + 9) = 15
    dp([1111], 2) = costs[2][0] = 6
  - min = 15
- min = min(∞, dp([1101], 2) + costs[3][2]) = min(23, 18 + 9) = 23
  dp([1101], 2)
  - for 반복문을 돈다. min = ∞
  - min = min(∞, dp([1111], 1) + costs[2][1]) = min(∞, 5 + 13) = 18
    dp([1111], 1) = costs[1][0] = 5
  - min = 18
- min = 23
min = 35

핵심 패턴

1️⃣ 비트마스크 DP 패턴

// 점화식의 상태
dp[mask][current] = 현재 위치까지의 최소 비용

// 최종 종료 조건
if (mask == (1 << n) - 1) return costs[current][0];

// 메모이제이션
if (dp[mask][current] != -1) return dp[mask][current];

// 점화식
for (int next = 0; next < n; next++) {
    if ((mask & (1 << next)) != 0) continue;  // 이미 방문
    min = Math.min(min, dp(mask | (1 << next), next) + costs[current][next]);
}

최적 부분 구조
- 전체 문제의 최적해가 부분 문제의 최적해로 구성됨을 기억해야 한다. 점화식 작성
중복 처리
- 같은 상태가 여러 경로로 도달 가능하여 메모이제이션 필요

2️⃣ 비트마스크 활용 패턴

// 방문 여부 확인
if ((mask & (1 << city)) != 0)
    
// 다음 상태로 변환해서 넘기기
dp((mask | (1 << next)), next)

// 모든 도시 방문 확인
if (mask == (1 << n) - 1)

3️⃣ 갈 수 없는 경우 처리

// 중간 경로에서 갈 수 없는 경우
if (costs[current][next] == 0) continue;

// 시작점으로 돌아갈 수 없는 경우
if (costs[current][0] == 0) return 100000000;

1차 제출 코드 ❌

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  static int n;
  static int[][] dp;
  static int[][] costs;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    costs = new int[n][n];
    dp = new int[1 << n][n];

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        costs[i][j] = sc.nextInt();
      }
    }

    for (int i = 0; i < (1 << n); i++) {
      Arrays.fill(dp[i], -1);
    }

    System.out.println(dp(1, 0));
    sc.close();
  }

  static int dp(int mask, int current) {
    if (mask == (1 << n) - 1) return costs[current][0];

    if (dp[mask][current] != -1) return dp[mask][current];

    int min = Integer.MAX_VALUE;
    for (int next = 0; next < n; next++) {
      if ((mask & (1 << next)) != 0) continue;
      min = Math.min(min, dp((mask | (1 << next)), next) + costs[current][next]);
    }
    return dp[mask][current] = min;
  }
}

문제의 조건인 갈 수 없는 경우 (W[i][j]=0)를 체크하지 못 했다.
- 이 경우 그 경로 자체를 누락시켜야 한다.
- 이 때 다시 처음으로 돌아갈 때도 갈 수 없는 경우가 있을 수 있다.
```
[0, 10, 15, 20]
[5,  0,  9, 10]
[6, 13,  0, 12]
[0,  8,  9,  0]
```
int min = Integer.MAX_VALUE;
- 오버플로우 발생 위험

최종 제출 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  static int n;
  static int[][] dp;
  static int[][] costs;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    costs = new int[n][n];
    dp = new int[1 << n][n];

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        costs[i][j] = sc.nextInt();
      }
    }

    for (int i = 0; i < (1 << n); i++) {
      Arrays.fill(dp[i], -1);
    }

    System.out.println(dp(1, 0));
    sc.close();
  }

  static int dp(int mask, int current) {
    if (mask == (1 << n) - 1) {
      if (costs[current][0] == 0) return 100000000;
      return costs[current][0];
    }

    if (dp[mask][current] != -1) return dp[mask][current];

    int min = 100000000;
    for (int next = 0; next < n; next++) {
      if ((mask & (1 << next)) != 0) continue;
      if (costs[current][next] == 0) continue;
      min = Math.min(min, dp((mask | (1 << next)), next) + costs[current][next]);
    }
    return dp[mask][current] = min;
  }
}