[백준 10971번] 외판원 순회 2

소스코드

---

1. DFS

#include <iostream>
using namespace std;
 
int n, map[11][11], visit[11], Min=98765432,cnt=0;
 
void dfs(int first, int a, int sum) {
    if (cnt == n && first == a) {
        if (Min > sum) {
            Min = sum;
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (visit[i]==0 && map[a][i]!=0) {
            visit[i] = 1;
            sum += map[a][i];
            cnt += 1;
            dfs(first,i,sum);
            visit[i] = 0;
            sum -= map[a][i];
            cnt -= 1;
        }
    }
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
        visit[i] = 0;
    }
 
    for (int i = 0; i < n; i++) {
        dfs(i,i,0);
    }
 
    cout << Min << '\n';
    return 0;
}

2. Permutation 이용

#include <iostream>
using namespace std;
#define swap(a,b,tmp) tmp=a; a=b; b=tmp;
 
int n,tmp,map[11][11],num[11],Min=98765432;
 
void perm(int* route, int start, int end) {
    if (start == end) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (map[route[i]][route[i + 1]] == 0 || map[route[n - 1]][route[0]] == 0) {
                return;
            }
            else if (i == n - 1) {
                sum += map[route[n - 1]][route[0]];
            }
            else {
                sum += map[route[i]][route[i + 1]];
            }
        }
        if (sum < Min) {
            Min = sum;
        }
        return;
    }
 
    for (int i = start; i <= end; i++) {
        swap(route[start], route[i], tmp);
        perm(route, start + 1, end);
        swap(route[start], route[i], tmp);
    }
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
        num[i] = i;
    }
    perm(num, 0, n - 1);
    cout << Min << '\n';
    return 0;
}