[백준] 2098번 외판원 순회 C++

문제 출처: https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

출발 노드를 임의로 정해도 되기 때문에 0번 노드를 출발 노드로 정했다.

또한 dp[현재 idx][방문 확인 bit셋]으로 메모이제이션을 한다.

TSP(만들 길이, 현재 idx, 방문 비트)를 작성하여 재귀적으로 풀었다.

 

1. base case인 leng== 0 인 경우 return 0;

2. leng == 1 인 경우 마지막 직전 idx에서는 출발지(노드 0번)으로 돌아와야 하기 때문에

출발지로 돌아올 수 있는지를 확인한다. 

3. 나머지 leng의 경우 이 때까지 간 적 없고 현재 노드에서 갈 수 있는 곳으로 보낸 뒤 그중 가장 작은 값을

dp[idx][bit]로 저장한다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>

using namespace std;

int dp[17][1 << 17];
int N;
int arr[17][17];
const int INF = 123456789;

int TSP(int leng, int idx, int visited) {
    if (leng == 0) {
        return 0;
    }
    if (dp[idx][visited] != -1)return dp[idx][visited];

    int val = INF;
    if (leng == 1) {
        //출발점으로 복귀 가능
        if (arr[idx][0] != 0)val = TSP(leng - 1, 0, visited) + arr[idx][0];
    }
    else {
        for (int i = 0; i < N; i++) {
            if (i == idx)continue;
            if (!(visited & (1<<i))) {
                if (arr[idx][i] != 0) {
                    val = min(val, TSP(leng - 1, i, visited | (1 << i)) + arr[idx][i]);
                }
            }
        }
    }

    return dp[idx][visited] = val;
    
}




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

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


    cout << TSP(N, 0, 1);
    


}