[ 백준 / C++ ] 10971 : 외판원 순회 2

[ 문제 ]

 

10971번: 외판원 순회 2

 

[ 접근방법 ]

 

흔한 백트래킹 문제다.

 

0번 도시에서 출발하여 다시 되돌아오는 비용을 일일히 비교한다.

 

[ 소스코드 ]

 

#include <iostream>

using namespace std;

int n, tsp[11][11], ans = 10000000;
bool chk[11];

void f(int idx, int x, int cnt){
    if(idx == n){
        if(!tsp[x][0]) return;
        cnt += tsp[x][0];
        ans = ans > cnt ? cnt : ans;
        return;
    }

    for(int i = 1; i < n; i++){
        if(!tsp[x][i] || chk[i])continue;

        chk[i] = true;
        f(idx + 1, i, cnt + tsp[x][i]);
        chk[i] = false;
    }
    
    return;
}

int main()
{
    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 >> tsp[i][j];

    f(1, 0, 0);

    cout << ans;

    return 0;
}