[C/C++] 백준 14889번 - 스타트와 링크 (DFS, 백트래킹, 비트마스킹, 브루트포스)

 

#include<iostream>
#include<math.h>
using namespace std;

int stats[21][21];
bool check[22];
int N;
int ans = 1000000000; // 10억

void DFS(int x, int pos) // x는 카운트 수, pos는 다음 값
{
	if (x == N / 2) // 카운트수가 정원의 1/2이 됐을 때 능력치합 계산
	{
		int start, link;
		start = 0;
		link = 0;

		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				if (check[i] == true && check[j] == true) start += stats[i][j];
				if (check[i] == false && check[j] == false) link += stats[i][j];
			}
		}

		int temp = abs(start - link);
		if (ans > temp) ans = temp;

		return;
	}

	for (int i = pos; i < N; i++)
	{
		check[i] = true;
		DFS(x + 1, i + 1);
		check[i] = false;
	}

}

int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> stats[i][j];
		}
	}

	DFS(0, 1); // 카운트 0회부터 숫자는 1부터 시작

	cout << ans;
}

 

각 팀마다의 능력치 합의 차이 최소치는 구할 수 있다고 쳐도 중복되지 않게 두 팀을 짜는 것이 이 문제의 관건이었다.
풀이는 DFS로 하였으며 check배열에 true로 표시된 값들은 모두 start팀이고 false로 표시된 팀은 link팀이다.  

팀을 나누기 위해 i의 범위는 pos(이후 값)부터 N-1까지 설정하였는데 N까지 설정할 경우 팀 배정에서 중복이 일어나기 때문에 N-1까지만 반복문을 돌린다. pos 값은 DFS로 인스턴스들이 넘어오기 전의 값을 기억해서 그 값보다 작은 수의 범위는 탐색하지 않게 하기 위해 필요한 값이다.

for (int i = pos; i < N; i++)
	{
		check[i] = true;
		DFS(x + 1, i + 1);
		check[i] = false;
	}

 

N=6인 경우를 예를 들어보면 

check배열을 print 했을 때 아래와 같이 나오게 된다.

어차피 두 팀 간의 능력치 합의 최소치를 구하는 문제이기 때문에 (start:1,2,3 / link:4,5,6)과 (start:4,5,6 / link:1,2,3) 중복에 해당되기 때문에 위와 같은 방식으로 중복되지 않게 팀을 나눌 수 있게 된다. 

그리고 x(카운트수)가 N/2가 되는 시점에서 2중 for문을 통해 check배열을 검사하여 같은 팀일 경우 각 팀의 능력치에 합하였고 이의 최솟값을 temp라는 변수에 저장하여 기존의 최솟값보다 작다면 새로 갱신할 수 있도록 코딩하였다.

 

www.acmicpc.net/problem/14889

14889번: 스타트와 링크