백준 2098번 [외판원 순회](C++) -yes6686- 티스토리

백준 문제 풀이: 2098 [외판원 순회]

---

문제 링크: https://www.acmicpc.net/problem/2098

문제 설명:

N개의 도시가 주어지고, 각 도시간의 이동 비용이 2차원 배열로 주어집니다. 1번 도시에서 출발하여 모든 도시를 한 번씩 방문한 뒤 다시 출발점으로 돌아오는 최소 비용을 구하는 문제입니다. 단, 이동할 수 없는 경우도 있을 수 있습니다.

---

문제 해결 코드

#include <iostream>
#include <cstring>
using namespace std;

int arr[16][16];
int dp[16][1 << 16];
int n;

int dfs(int x, int visit) {
    if (visit == (1 << n) - 1) {
        if (arr[x][0] == 0) {
            return 1e9; // 출발지로 돌아갈 수 없는 경우
        }
        return arr[x][0]; // 출발지로 돌아가는 비용
    }
    if (dp[x][visit] != -1) {
        return dp[x][visit];
    }
    dp[x][visit] = 1e9;

    for (int i = 0; i < n; i++) {
        if (arr[x][i] == 0) continue; // 이동할 수 없는 경우
        if (visit & (1 << i)) continue; // 이미 방문한 도시
        dp[x][visit] = min(dp[x][visit], arr[x][i] + dfs(i, visit | (1 << i)));
    }
    return dp[x][visit];
}

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));

    cout << dfs(0, 1) << '\n'; // 0번 도시에서 출발하여 모든 도시를 방문
}

예제

입력:
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

출력:
80

---

코드 설명

• DP 정의: dp[x][visit]는 현재 도시 x에서 시작하여 visit에 포함되지 않은 도시를 모두 방문하고 출발점으로 돌아가는 최소 비용입니다.
• DFS 사용: 재귀적으로 현재 도시에서 이동 가능한 도시를 탐색하며 최소 비용을 갱신합니다.
• 비트마스크: 방문 여부를 비트마스크로 관리하여 모든 도시 방문 상태를 효율적으로 표현합니다.
• 기저 조건: 모든 도시를 방문한 경우, 출발점으로 돌아가는 비용을 반환합니다.

시간 복잡도

• 전체 시간 복잡도는 O(N * 2^N)으로, N이 최대 16이므로 충분히 처리 가능합니다.

---

결과

이 코드는 외판원 순회 문제를 비트마스크와 DP를 활용하여 효율적으로 해결합니다. 모든 도시를 방문하고 출발점으로 돌아오는 최소 비용을 정확히 계산합니다.