백준) 14889.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <utility>

#define MAX 21

bool ck[MAX];
bool visited[MAX];
int map[MAX][MAX];
int arr[MAX];
int min = 2147483647;
int n;

int cal(std::vector<int> &vec, int idx)
{
    int ans = 0;

    for (int i = 0; i < vec.size(); ++i)
    {
        for (int j = 0; j < vec.size(); ++j)
        {
            if (i != j)
                ans += map[vec[i]][vec[j]];
        }
    }

    return (ans);
}

int team()
{
    std::vector<int> start;
    std::vector<int> link;

    for (int i = 1; i < n + 1; ++i)
    {
        if (ck[i] == true)
            start.push_back(i);
        else
            link.push_back(i);
    }

    int s = cal(start, 1);
    int l = cal(link, 1);

    // for (int i = 0; i < start.size(); ++i)
    //     std::cout << start[i] << " ";
    // std::cout << "\n";
    return (std::abs(s - l));
}

void sol(int num, int idx)
{
    if (idx == n / 2)
    {
        // for (int i = 1; i < n + 1; ++i)
        // {
        //     if (ck[i])
        //         std::cout << i << " ";
        // }
        // std::cout << "\n";
        int t = team();
        if (t < min)
            min = t;
        return;
    }
    for (int i = num; i < n + 1; ++i)
    {
        if (!ck[i])
        {
            ck[i] = true;
            sol(i, idx + 1);
            ck[i] = false;
        }
    }
}

int main()
{
    std::cin >> n;

    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = 1; j < n + 1; ++j)
            std::cin >> map[i][j];
    }
    sol(1, 0);
    std::cout << min << "\n";
}