백준-스타트와 링크.cpp.txt

// ConsoleApplication3.cpp: 콘솔 응용 프로그램의 진입점을 정의합니다.
//
#include<iostream>
#include<string.h>
#include<string>
#include<queue>
#include<utility>
#include<math.h>
using namespace std;
int N;
int arr[21][21];
bool check[11];
int start_t[11];
int link_t[11];
int num[21];
int result = 1000000001;

void go(int x, int depth)
{
	if (depth == N/2)
	{
		for (int i = 1; i <= N; i++)
		{
			num[i] = i;
		}
		int start_num = 0;
		int link_num = 0;

		for (int i = 1; i <= N / 2; i++)
		{
			for (int j = i + 1; j <= N / 2; j++)
			{
				int s = start_t[i];
				int k = start_t[j];
				for (int i = 1; i <= N; i++)
				{
					if (num[i] == s || num[i] == k)
					{
						num[i] = 0;
					}
				}
				start_num += arr[s][k] + arr[k][s];
			}
		}
		int t = 1;
		for (int i = 1; i <= N; i++)
		{
			if (t > N / 2)
			{
				break;
			}
			if (num[i] != 0)
			{
				link_t[t] = num[i];
				t++;
			}
		}
		for (int i = 1; i <= N / 2; i++)
		{
			for (int j = i + 1; j <= N / 2; j++)
			{

				int s = link_t[i];
				int k = link_t[j];
				link_num += arr[s][k] + arr[k][s];
			}
		}
		int re = abs(link_num - start_num);
		if (re < result)
			result = re;
		
		return;
	}

	for (int i = 1; x+i <= N; i++)
	{
		if (check[x + i] == false)
		{
			check[x + i] = true;
			start_t[depth+1] = x + i;
			go(x + i, depth + 1);

			check[x + i] = false;
			
		}

	}

	
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		num[i] = i;
	}
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i <= N; i++)
	{
		check[i] = false;
	}

	go(0,0);

	cout << result << endl;
	return 0;
}