14889 스타트와 링크

순열, dfs 모두 가능

bm을 이용해 dfs로 풀었다.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, s[20][20], ans = 2e9;
 
void solve(int bm, int x, int cnt) {
    if (cnt > n / 2 || x >= n) return;
    if (cnt == n / 2) {
        int sum[2] = { 0, }, b[20];
        for (int i = 0; i < n; i++) b[i] = bm&(1 << i) ? 1 : 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (b[i] != b[j]) continue;
                sum[b[i]] += s[i][j];
                sum[b[i]] += s[j][i];
            }
        }
        ans = min(ans, abs(sum[0] - sum[1]));
        return;
    }
    solve(bm | (1 << x), x + 1, cnt + 1);
    solve(bm, x + 1, cnt);
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        scanf("%d", &s[i][j]);
    solve(0, 0, 0);
    printf("%d", ans);
    return 0;
}