백준 14889 스타트와 링크

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

 

서론

완전탐색 문제.

 

---

풀이

스타트와 링크팀을 만들 수 있는 모든 경우의 수를 재귀를 이용한 완전탐색으로 구현한다.

그리고 팀의 구분은 배열로 만들 수 있는데, 하나의 배열에 1의 팀과 0의 팀으로 구분할 수 있다.

team{1, 1, 0, 0}은 1,2가 1팀, 3,4가 0팀

team{1, 0, 0, 1}은 1,4가 1팀, 2,3이 0팀

void dfs(int idx, int cnt, bool tf){
    if(tf == true) team[idx] = 1;
    else team[idx] = 0;
    
    if(cnt == n/2) 팀별 계산하고 리턴;
    else if(idx == n) return
    
    dfs(idx+1, cnt+1, true);
    dfs(idx+1, cnt, false);
}

 

그 후 1팀의 능력치 합은 아래 코드와 같고 0팀의 합도 같은 원리이며 얻어진 합으로 1팀과 0팀의 차이값을 계산한다. 이 과정을 모든 경우의 수에 실행한다.

for (int i = 1; i <= n; i++) {
	if (team[i] == 0) continue;
	for (int j = 1; j <= n; j++) {
		if (i != j && team[j] != 0) {
			sumA += map[i][j];
		}
	}
}

team 배열의 왼쪽부터 순차적으로 탐색하며 한 팀원을 선택하고 그 팀원과 같은 팀에 속한 팀원들의 능력치들을 다 더한다.

예를들어 1번과 3번이 같은 팀이라면

1번을 선택했을때 같은 팀에 속한 능력치들을 더하는 과정에서 S13이 더해지고

3번을 선택했을때 같은 팀에 속한 능력치들을 더하는 과정에서 S31이 더해진다.

 

---

구현

// c++

#include <iostream>
#include <algorithm>

using namespace std;

int map[100][100];
int team[101];
int n;
int result = 0x7f7f7f7f;

void init() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
}

int cal() {
	int sumA = 0;
	int sumB = 0;
	for (int i = 1; i <= n; i++) {
		if (team[i] == 0) continue;
		for (int j = 1; j <= n; j++) {
			if (i != j && team[j] != 0) {
				sumA += map[i][j];
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (team[i] == 1) continue;
		for (int j = 1; j <= n; j++) {
			if (i != j && team[j] != 1) {
				sumB += map[i][j];
			}
		}
	}
	//cout << sumA << " " << sumB << endl;
	return abs(sumA - sumB);
}

void dfs(int idx, int cnt, bool tf) {
	if (tf == true) team[idx] = 1;
	else team[idx] = 0;

	if (cnt == n / 2) {
		/*
		cout << idx << endl;
		for (int i = 1; i <= n; i++) {
			cout << team[i] << " ";
		}
		cout << endl;
		*/
		result = min(result, cal());
		return; 
	}
	else if (idx == n) {
		return;
	}
	
	dfs(idx + 1, cnt + 1, true);
	dfs(idx + 1, cnt, false);

	return;
	
}

int main() {
	init();
	dfs(0, 0, 1);
	cout << result;
}