인프런 커뮤니티 질문&답변

정말 감사드립니다!!

안녕하세요 mch님 ㅎㅎ

#include <bits/stdc++.h> 
#define MAX_N 16
const int INF = 987654321;
using namespace std; 
int n, dp[MAX_N][1 << MAX_N], dist[MAX_N][MAX_N];
int tsp(int here, int visited){
    if(visited == (1 << n) - 1){
        return dist[here][0] ? dist[here][0] : INF;
    }
    int &ret = dp[here][visited];
    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;
        int temp = tsp(i, visited | (1 << i));
        cout << "temp : " << temp << "\n";
        ret = min(ret, temp + dist[here][i]);
        cout << (visited | (1 << i)) << " : " << ret << "\n";
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> dist[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    cout << tsp(0, 1) << '\n';
    return 0;
}

한번 이렇게 해보시겠어요?

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.