14889번 스타트와 링크

이 문제는 완전탐색이였다. dfs도 필요했다. 완전 탐색도 생각보다 오래걸릴 수 있다는 것을 보여준 문제였다.

// 14889번 스타트와 링크
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
int n;
int arr[101][101];
int team[21] = {0};
int MIN = 987654321;
// 0 -> start 1-> link
void matchTeam(int index, int remain) {
  remain--;
  // 팀 비교를 해줘야함.
  if (!remain) {
    team[index] = 1;

    int start = 0, link = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (team[i] == team[j] && team[i] == 0) {
          start += arr[i][j];
        }
        if (team[i] == team[j] && team[i] == 1) {
          link += arr[i][j];
        }
      }
    }

    int res = abs(start - link);
    MIN = min(MIN, res);
  } else {
    team[index] = 1;
    for (int i = index + 1; i <= n - remain; i++) {
      matchTeam(i, remain);
    }
  }
  team[index] = 0;
  return;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> arr[i][j];
    }
  }
  matchTeam(0, n / 2);
  cout << MIN << endl;
  return 0;
}