[BOJ]14889번: 스타트와 링크 (c++)

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

14889번: 스타트와 링크

 

방법 1: 백트랙킹

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

using namespace std;

const int MAX = 20;
int min_dif = 1000;
int S[MAX][MAX];
int N;

// 점수 차이 구하기
int get_point_dif(vector<int>& team_s, vector<int>& team_l)
{
	int sum_s = 0;
	int sum_l = 0;
	for (int i = 0; i < team_s.size(); ++i)
	{
		for (int j = 0; j < team_s.size(); ++j)
		{
			sum_s += S[team_s[i]][team_s[j]];
			sum_l += S[team_l[i]][team_l[j]];
		}
	}
	return abs(sum_s - sum_l);
}

void dfs(vector<int> & team_s, vector<int> &team_l, int index)
{
	if (index == N)
	{
		// 각 팀이 모두 N / 2명이 아니면 X
		if (team_s.size() != N / 2 || team_l.size() != N / 2)
		{
			return;
		}

		// 최소 점수차이 구하기
		min_dif = min(min_dif, get_point_dif(team_s, team_l));

		return;
	}

	// index번째의 선수가 team_s에 속했을 때
	team_s.push_back(index);
	dfs(team_s, team_l, index + 1);
	team_s.pop_back();

	// index번째의 선수가 team_l에 속했을 때
	team_l.push_back(index);
	dfs(team_s, team_l, index + 1);
	team_l.pop_back();
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> S[i][j];
		}
	}

	// dfs - 백트랙킹으로 선수 조합해서 팀만들기
	vector<int> team_s, team_l;
	dfs(team_s, team_l, 0);

	cout << min_dif;

	return 0;
}

 

방법 2: 비트마스크

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

using namespace std;

// 두 팀의 점수 차이 구하기
int get_dif(vector<vector<int>> &S, int bitset)
{
	int team_s = 0;
	int team_l = 0;
	int len = S.size();

	for (int i = 0; i < len; ++i)
	{
		for (int j = i; j < len; ++j)
		{
			// 비트가 1이면 team_s에 점수 합산
			if (bitset & ((1 << i) | (1 << j)))
			{
				team_s += S[i][j] + S[j][i];
			}
			// 비트가 0이면 team_l에 점수 합산
			if (~bitset & ((1 << i) | (1 << j)))
			{
				team_l += S[i][j] + S[j][i];
			}
		}
	}
	// 차이의 절대값 반환
	return abs(team_s - team_l);
}

// 1의 개수가 N / 2이면 true
bool check(int bitset, int N)
{
	int cnt = 0;
	for (int i = 0; i < N; ++i)
	{
		if (bitset & (1 << i))
		{
			++cnt;
		}
	}
	return cnt == N / 2;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N;
	cin >> N;
	vector<vector<int>> S(N, vector<int>(N));
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> S[i][j];
		}
	}

	// 비트마스크로 팀 조합 구하기
	int min_dif = 2000;
	for (int i = 1; i < (1 << N); ++i)
	{
		// 1의 개수가 N / 2이면 true
		if (check(i, N))
		{
			// 차이의 최소값 구하기
			min_dif = min(min_dif, get_dif(S, i));
		}
	}

	cout << min_dif;

	return 0;
}

 

방법 3 : 순열

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

using namespace std;

enum {A, B};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N;
	cin >> N;
	vector<vector<int>> point(N, vector<int>(N));
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> point[i][j];
		}
	}
	
	// mem벡터의 앞 절반은 0, 뒤 절반은 1로 초기화
	vector<int> mem(N, 1);
	for (int i = 0; i < N / 2; ++i)
	{
		mem[i] = 0;
	}

	// 순열로 멤버들이 팀을 선택하는 다양한 경우의 수 구해서 점수차이 계산
	int min_dif = 987654321;
	do {
		vector<int> teamA, teamB;
		for (int i = 0; i < N; ++i)
		{
			// 0 -> team A, 1 -> team B
			if (mem[i] == A)
			{
				teamA.push_back(i);
			}
			else
			{
				teamB.push_back(i);
			}
		}
		
		int pA = 0, pB = 0;
		for (int i = 0; i < N / 2; ++i)
		{
			for (int j = 0; j < N / 2; ++j)
			{
				pA += point[teamA[i]][teamA[j]];
				pB += point[teamB[i]][teamB[j]];
			}
		}

		// 최소차이 구하기
		min_dif = min(min_dif, abs(pA - pB));
	
	} while (next_permutation(mem.begin(), mem.end()));

	cout << min_dif;

	return 0;
}

 

속도 순위는 1. 백트랙킹 2. 순열 3. 비트마스크 순으로 빠르다.

 

 

 

TIP_백트랙킹

이 문제는 X를 팀 A에 포함시킬거냐, 아니면 팀 B에 포함시킬거냐를 결정해야 하는 문제이다. 

다른 백트랙킹 문제와 마찬가지로, 

선택 A를 했다가 선택 B로 넘어갈 때는 원상복구를 잘 해줘야 한다.

 

 

TIP_비트마스크

팀이 2개 밖에 없으므로 , 비트마스크를 사용할 수 있다.

다만 팀원 수를 카운팅 하는 메소드를 따로 작성해주어야 하는 번거로움이 있다.

ex) N이 4일때 1000은 팀원 수가 1 : 3 이므로 X