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

📌 외판원 문제 (TSP, Traveling Salesman Problem)? 🚀

🔹 문제 개요:

• 어떤 한 도시에서 출발하여 모든 도시를 한 번씩 방문한 뒤, 다시 출발 도시로 돌아오는 최단 경로를 찾는 문제

---

✅ 1. 문제 설명

🎯 문제 예제

어떤 도시들이 있고, 도시 간 이동 비용(거리)이 주어진다고 하자.

📌 예제 입력 (도시 4개, 거리 행렬)

  0   1   2   3
0 [0, 10, 15, 20]
1 [10, 0, 35, 25]
2 [15, 35, 0, 30]
3 [20, 25, 30, 0]

각 값 dist[i][j]는 도시 i에서 j로 가는 비용을 의미한다.
예를 들어:

• dist[0][1] = 10 → 0번 도시에서 1번 도시로 가는 비용 10
• dist[2][3] = 30 → 2번 도시에서 3번 도시로 가는 비용 30

---

✅ 2. 문제 목표

✔ 모든 도시를 정확히 한 번씩 방문한 후, 다시 출발 도시로 돌아오는 최소 비용 경로를 찾는 것
✔ 즉, 가장 짧은 "순회 경로"를 찾는 것!

---

✅ 3. 가능한 경로 예시

🚗 가능한 방문 순서 & 비용 계산

(1) 경로: 0 → 1 → 2 → 3 → 0

비용: 0 → 1 (10) + 1 → 2 (35) + 2 → 3 (30) + 3 → 0 (20) = 95

(2) 경로: 0 → 2 → 1 → 3 → 0

비용: 0 → 2 (15) + 2 → 1 (35) + 1 → 3 (25) + 3 → 0 (20) = 95

(3) 경로: 0 → 1 → 3 → 2 → 0

비용: 0 → 1 (10) + 1 → 3 (25) + 3 → 2 (30) + 2 → 0 (15) = 80 ✅ 최소 비용!

📌 즉, 최소 비용 경로는 0 → 1 → 3 → 2 → 0이며, 비용은 80! 🚀

---

✅ 4. 문제의 특징

✔ "모든 도시를 방문해야 한다" → 단순한 최단 경로 문제와 다름
✔ "한 번 방문한 도시는 다시 방문하면 안 된다"
✔ "모든 경로를 탐색해야 할 수도 있음 (완전 탐색 필요)"
✔ "비트마스크 + DP를 사용하면 최적화 가능"

---

✅ 5. 문제의 입력과 출력 형식

🔹 입력 형식

N    // 도시 개수 (1 ≤ N ≤ 16)
dist // N x N 크기의 거리 행렬

📌 예제 입력

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

---

🔹 출력 형식

최소 이동 비용을 출력

📌 예제 출력

80

---

✅ 6. 문제 해결 방법

✔ 완전 탐색 (Brute Force, 순열)

• 모든 방문 순서를 직접 생성해보고 최소 비용을 찾음
• 시간 복잡도 O(N!) (비효율적)

✔ DP + 비트마스크 (O(N^2 * 2^N))

• dp[i][visited]를 사용해 최소 비용을 저장
• 비트마스크(int visited)를 사용해 방문 상태를 효율적으로 저장
• dp[i][visited]에 i번 도시에서 특정 방문 상태일 때의 최소 비용을 저장하여 중복 계산을 방지!

---

✅ 7. 코드 예제 (DP + 비트마스크)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 987654321
#define MAX_N 16

int n, dist[MAX_N][MAX_N];
int dp[MAX_N][1 << MAX_N]; // dp[i][visited]: i번 도시에서 visited 상태일 때 최소 비용

// 외판원 문제 해결 (DP + 비트마스크)
int tsp(int here, int visited) {
    if (visited == (1 << n) - 1) { // 모든 도시 방문 완료
        return dist[here][0] ? dist[here][0] : INF; // 시작 도시로 복귀
    }

    int& ret = dp[here][visited]; // DP 값 참조
    if (ret != -1) return ret; // 이미 계산된 경우 반환
    ret = INF;

    for (int i = 0; i < n; i++) {
        if (visited & (1 << i)) continue; // 이미 방문한 도시면 건너뜀
        if (dist[here][i] == 0) continue; // 이동할 수 없는 도시 건너뜀
        ret = min(ret, tsp(i, visited | (1 << i)) + dist[here][i]); // 최소 비용 갱신
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }

    fill(&dp[0][0], &dp[MAX_N - 1][(1 << MAX_N)], -1); // DP 배열 초기화
    cout << tsp(0, 1) << '\n'; // 0번 도시에서 시작하여 최소 비용 계산

    return 0;
}

---

✅ 8. 코드 실행 흐름

📌 입력:

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

📌 연산 흐름:
1️⃣ tsp(0, 0001) → 0번 도시 방문 후 탐색
2️⃣ tsp(1, 0011) → 1번 도시 방문 후 탐색
3️⃣ tsp(3, 1011) → 3번 도시 방문 후 탐색
4️⃣ tsp(2, 1111) → 2번 도시 방문 후 시작 도시(0)로 복귀
5️⃣ 최소 비용 80 반환

📌 출력:

80

---

🎯 9. 최종 정리

✔ 외판원 문제(TSP)는 "모든 도시를 한 번씩 방문하고 출발 도시로 돌아오는 최소 비용 경로"를 찾는 문제
✔ 완전 탐색(O(N!))은 비효율적이므로 DP + 비트마스크(O(N^2 * 2^N))를 사용하면 최적화 가능
✔ 비트마스크(int visited)를 활용하면 방문 상태를 정수 하나로 표현하여 효율적인 DP 테이블 관리 가능
✔ 최종 결과: 입력 예제의 경우 최소 비용은 80! 🚀🔥

---