[BOJ] #14889 _ 스타트와 링크

[스타트와 링크] https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

dfs를 이용하는 문제이다.

 

next_permutation을 이용하면 더 쉽게 구현할 수 있지만,

{a, a, a, b, b, b}와 {b, b, b, a, a, a}를 중복 계산한다.

(단, 중복 계산해도 시간 초과는 발생하지 않기 때문에 사용해도 된다.)

 

중복 계산하지 않도록 구현하기 위해 아래와 같이 재귀 함수를 이용하여 구현하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAX 21
#define INF 999999999

using namespace std;

int n, result = INF;
int s[MAX][MAX], chk[MAX];

void solve(int cnt, int idx);
void getScore();
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) scanf("%d", &s[i][j]);
	}

	chk[1] = 1;
	solve(1, 1);
	printf("%d\n", result);

	return 0;
}

void solve(int cnt, int idx) {
	if (cnt == n / 2) {
		getScore();
		return;
	}

	for (int i = idx + 1; i <= n; i++) {
		chk[i] = 1;
		solve(cnt + 1, i);
		chk[i] = 0;
	}
}

void getScore() {
	int start = 0, link = 0;

	for (int i = 1; i <= n; i++) {
		int val = 0;
		for (int j = 1; j <= n; j++) {
			if (chk[i] != chk[j]) continue;
			val += s[i][j];
		}
		if (chk[i]) start += val;
		else link += val;
	}

	result = min(result, abs(start - link));
}