[SWEA] 스타트와 링크

문제링크 : https://www.acmicpc.net/problem/14889

💻 문제 풀이 : C++

#include <iostream>
#define MAX 21

using namespace std;

int MAP[MAX][MAX];
int N, teamCnt;
int minAns = 2134567890;
int team[MAX];

int abs(int a)
{
	return a > 0 ? a : -a;
}

int getAns()
{
	int start[MAX / 2] = { 0 };
	int start_idx = 0;
	int link[MAX / 2] = { 0 };
	int link_idx = 0;

	for (int i = 0; i < N; i++)
	{
		if (team[i] == 0)
			start[start_idx++] = i;
		else
			link[link_idx++] = i;
	}
	int startVal = 0;
	for (int i = 0; i < N / 2; i++)
		for (int j = i + 1; j < N / 2; j++)
			startVal += MAP[start[i]][start[j]] + MAP[start[j]][start[i]];
	
	int linkVal = 0;
	for (int i = 0; i < N / 2; i++)
		for (int j = i + 1; j < N / 2; j++)
			linkVal += MAP[link[i]][link[j]] + MAP[link[j]][link[i]];

	return abs(startVal - linkVal);
}

void DFS(int level)
{
	if (level == N)
	{
		int teamCnt = 0;
		for (int i = 0; i < N; i++)
		{
			if (team[i] == 0)
				teamCnt++;
		}
		if (teamCnt != N / 2)
			return;
		int tmp = getAns();
		if (minAns > tmp) minAns = tmp;
		return;
	}
	for (int i = 0; i < 2; i++)
	{
		team[level] = i;
		DFS(level + 1);
		team[level] = 0;
	}
}

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> MAP[i][j];

	DFS(0);
	cout << minAns << "\n";

	return 0;
}