(c++)백준 14889번: 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

[풀이]

dfs 조합으로 모든 경우의 수를 탐색하는 문제였다.

매 경우의 수마다 스타트 팀과 링크 팀의 능력치 차를 계산하여 최소값을 갱신한다.

 

#include <iostream>
#include <algorithm>//min
#include <cstdlib>//abs
using namespace std;

int N;
int S[21][21];
bool Select[21];//스타트 팀에 속한 사람
int totalS = 0;
int Min = 987654321;

void getDiff() {
	int Start = 0;
	int Link = 0;
	for (int i = 1; i <= N; i++) {
		if (Select[i] == true) {
			for (int j = 1; j <= N; j++) {
				if (i == j)
					continue;
				if (Select[j] == true) {
					Start += S[i][j];
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if (Select[i] == false) {
			for (int j = 1; j <= N; j++) {
				if (i == j)
					continue;
				if (Select[j] == false) {
					Link += S[i][j];
				}
			}
		}
	}
	int diff = abs(Start - Link);
	Min = min(Min, diff);
}

void setStart(int idx, int cnt) {
	if (cnt == N / 2) {
		getDiff();
		return;
	}
	for (int i = idx; i <= N; i++) {
		if (Select[i] == true)
			continue;
		Select[i] = true;
		setStart(i, cnt + 1);
		Select[i] = false;
	}
}

void solution() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> S[i][j];
		}
	}
	setStart(1, 0);
	cout << Min << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}