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

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int travelCnt(int* arr, int col){ // 비용 계산

return arr[col];

}

int fib(int cnt) {

if (cnt > 0)

return cnt * fib(cnt-1);

else

return 1;

}

int main() {

int N;

cin >> N;

int W[N][N];

vector <int> v(N);

int arrSize = fib(N);

int arr[arrSize][N+1];

bool isZero = false; // 경로에 0이 있는가

for (int i = 0; i < N; i++)

v[i] = i;

int index = 0;

int cost[arrSize];

do{ // 모든 경로의 경우의 수에 다시 처음 지점으로 되돌아 오는 도시를 추가한 순열

for (int i = 0; i < N+1; i++) {

if (i == N)

arr[index][i] = arr[index][0];

else

arr[index][i] = v[i];

}

index++;

} while(next_permutation(v.begin(), v.end()));

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++)

cin >> W[i][j];

}

int min = 10000000;

for (int i = 0; i < arrSize; i++) {

int sum = 0;

for (int j = 0; j < N; j++) {

if (travelCnt(W[arr[i][j]], arr[i][j+1]) != 0)

sum += travelCnt(W[arr[i][j]], arr[i][j+1]);

else { // 경로 중에 0이 있으면 갈 수 없다!

isZero = true;

break;

}

}

if (isZero) {

sum = 0;

isZero = false;

continue;

}

else {

cost[i] = sum;

if (min > sum)

min = sum;

}

sum = 0;

}

cout << min << endl;

}