[백준] 14889 - 스타트와 링크

dfs의 기본문제라고 생각된 문제

1. N/2로 팀을 나눈다

2. 2중포문으로 start팀과 link 팀의 능력치를 구하고, 차이의 최소값을 구한다

#include <iostream>
#define MX 22
#define INF 987654321
#define ABS(X) (X) > 0? (X): -(X)
using namespace std;
 
bool check[MX];
int map[MX][MX];
int N, dab = INF;
 
void dfs(int d, int pos)
{
    if (d == N / 2)
    {
        int start, link;
        start = link = 0;
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (check[i] && check[j]) start += map[i][j];
                if (!check[i] && !check[j]) link += map[i][j];
            }
        }
        int tmp = ABS(start - link);
        if (tmp < dab) dab = tmp;
        return;
    }
    for (int i = pos; i < N; i++)
    {
        check[i] = true;
        dfs(d + 1, i + 1);
        check[i] = false;
    }
}
 
int main(void)
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> map[i][j];
    dfs(0, 1);
    cout << dab << endl;
    return 0;
}