[백준/백트래킹/C++] 10971번 외판원 순회2 *

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

#include <bits/stdc++.h>

using namespace std;

int n;
bool ch[11];
int ans = 1e9;
int w[10][10];

void go(int start, int index, int cnt, int sum) { // 최초 출발지점, 현재 위치, 지나간 마을수, 이동비용
    if(cnt == n){
        if(w[index][start] == 0) return;
        if(ans > sum + w[index][start]) ans = sum + w[index][start];
        return;
    }
    for(int i=0; i<n; i++){
        if(ch[i] || w[index][i]==0) continue;
        ch[i] = 1;
        go(start, i, cnt+1, sum+w[index][i]);
        ch[i] = 0;
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    for(int i=0; i<n; i++){
        ch[i] = 1;
        go(i, i, 1, 0); // 최초 출발지점, 현재 위치, 지나간 마을수, 이동비용
        ch[i] = 0;
    }
    cout << ans;

    return 0;
}