[BOJ] 14889 스타트와 링크

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

14889번: 스타트와 링크

아이디어

방법1 dfs를 이용하여 팀이 될 수 있는 모든 경우의 수를 구한 다음 능력치의 차이를 계산

 - 기존 시작 시에는 다들 0번 팀이라고 배치하고 팀을 부여함

 - 재귀문을 통하여 한사람씩 1번 팀을 경우의 수마다 부여를 하고 해당 인원의 반이 1번팀의 배치가 되었으면 능력치       차이를 계산

 

방법2 비트 마스킹 방법을 이용하여 팀을 구분한 다음 능력치의 차이를 계산

 

-예시 : 110100

 

- 오른쪽부터 왼쪽 순으로 사람의 번호가 1번부터 시작된다고 생각 후 0이면 0번팀, 1이면 1번팀에 배정이 되았다고 생각

- 1,2,4,번 사람은 0번팀 / 3,5,6번 사람은 1번팀

- 위와 같이 판단 후 능력치의 차이를 계산

 

소스코드

방법1

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

int num;
int map[21][21];
int diff = -1;
int team[21];


void dfs(int team_cnt, int start) {


	//쌍이 지어지면 그 차이를 구함
	if (team_cnt == (num / 2)) {

		int sum1 = 0;
		int sum2 = 0;
		int temp_diff;

		vector<int> team1;
		vector<int> team2;


		for (int i = 0; i < num; i++) {
			if (team[i] == 0) {
				team1.push_back(i);
			}
			else if (team[i] == 1) {
				team2.push_back(i);
			}
		}

		int s1 = team1.size();
		int s2 = team2.size();

		for (int i = 0; i < s1; i++) {
			for (int j = i + 1; j < s1; j++) {
				sum1 += (map[team1[i]][team1[j]] + map[team1[j]][team1[i]]);
			}
		}

		for (int i = 0; i < s2; i++) {
			for (int j = i + 1; j < s2; j++) {
				sum2 += (map[team2[i]][team2[j]] + map[team2[j]][team2[i]]);
			}
		}

		temp_diff = abs(sum1 - sum2);

		if (diff == -1 || temp_diff < diff) {
			diff = temp_diff;

		}

		return;
	}


	for (int i = start + 1; i < num; i++) {
		team[i] = 1;
		dfs(team_cnt + 1, i);
		team[i] = 0;
	}

}


int main() {
	scanf("%d", &num);

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			scanf("%d", &map[i][j]);
		}
	}


	dfs(0, -1);

	printf("%d\n", diff);


	return 0;
}

방법2

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

int num;
int map[21][21];
int diff = -1;
vector<int> team1;
vector<int> team2;


void set_team(int group) {

	for (int i = 0; i < num; i++) {

		if (group % 2 == 0) {
			team1.push_back(i);
		}
		else {
			team2.push_back(i);
		}
		group = group >> 1;
	}

}

void calc_diff() {
	int s1 = team1.size();
	int s2 = team2.size();
	int sum1 = 0;
	int sum2 = 0;
	int temp_diff;

	for (int i = 0; i < s1; i++) {
		for (int j = i + 1; j < s1; j++) {
			sum1 += (map[team1[i]][team1[j]] + map[team1[j]][team1[i]]);
		}
	}

	for (int i = 0; i < s2; i++) {
		for (int j = i + 1; j < s2; j++) {
			sum2 += (map[team2[i]][team2[j]] + map[team2[j]][team2[i]]);
		}
	}

	temp_diff = abs(sum1 - sum2);

	if (diff == -1 || temp_diff < diff) {
		diff = temp_diff;

	}
}



int main() {
	scanf("%d", &num);

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			scanf("%d", &map[i][j]);
		}
	}


	for (int i = 0; i < pow(2, num); i++) {
		team1.clear();
		team2.clear();

		set_team(i);
		if (team1.size() != num / 2) continue;
		calc_diff();

	}



	printf("%d\n", diff);


	return 0;
}