[c++/백준] 14889 스타트와 링크

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

팀 나누고 최솟값 구하는게 중요한 것 같다. 

#include <iostream>
#include <cmath>
using namespace std;

int n;
int arr[21][21];
bool isVisited[22];
int minNum = 10000000;	//최솟값 찾기 위함

void dfs(int x, int idx) {
	if (x == n / 2) {
		int start, link;
		start = 0;
		link = 0;
        
        //start와 link 팀 나누기
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (isVisited[i] == true && isVisited[j] == true) {
					start += arr[i][j];
				}
				if (isVisited[i] == false && isVisited[j] == false) {
					link += arr[i][j];
				}
			}
		}
		int temp = 0;
		temp = abs(start - link);
		if (temp < minNum)
			minNum = temp;
	}
    //백트래킹
	for (int i = idx; i < n; i++) {
		isVisited[i] = true;
		dfs(x + 1, i + 1);
		isVisited[i] = false;
	}
}

int main() {
	cin >> n;
	
    //인접리스트
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}
	dfs(0, 1);
	cout << minNum;
}