C++ 14889 스타트와 링크 [DFS, 백트래킹]

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>


void DFS(std::vector<std::vector<int>>& _StartLink, std::vector<bool>& _TeamCheck, int& _result, int _index, int _count)
{
	std::vector<int> Start;
	std::vector<int> Link;
	
	int Start_Sum = 0;
	int Link_Sum = 0;

	int N = _TeamCheck.size();

	if(_count==(N/2))
	{
		for (int i = 0; i < N; i++)
		{
			if (true == _TeamCheck[i])
			{
				Start.push_back(i);
			}
			else
			{
				Link.push_back(i);
			}
		}

		for (int i = 0; i < (N/2); i++)
		{
			for (int j = 0; j < (N/2); j++)
			{
				Start_Sum += _StartLink[Start[i]][Start[j]];
				Link_Sum += _StartLink[Link[i]][Link[j]];
			}
		}

		if (_result == -1)
		{
			_result = abs(Start_Sum - Link_Sum);
		}
		else
		{
			_result = std::min(_result, abs(Start_Sum - Link_Sum));
		}

		return;
	}

	for (int i = _index; i < N; i++)
	{
		if (false == _TeamCheck[i])
		{
			_TeamCheck[i] = true;
			DFS(_StartLink, _TeamCheck, _result, i, _count + 1);
			_TeamCheck[i] = false;
		}
	}
}

int main()
{
	std::vector<std::vector<int>> StartLink;
	std::vector<bool> TeamCheck;
	int result = -1;

	int N;

	std::cin >> N;

	StartLink.resize(N);
	TeamCheck.resize(N);

	for (int i = 0; i < N; i++)
	{
		StartLink[i].resize(N);

		for (int j = 0; j < N; j++)
		{
			std::cin >> StartLink[i][j];
		}
	}

	DFS(StartLink, TeamCheck, result, 0, 0);

	std::cout << result << "\n";

	return 0;


}