[백준 BOJ][C++]14889번 스타트와 링크 풀이: DFS

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

14889번: 스타트와 링크

 

이 문제는 DFS로 해결할 수 있습니다. 

 

먼저 0~n-1의 index 중 n/2 길이의 조합을 탐색합니다. 

 

n = 4 일 때 0, 1, 2, 3 중 길이 2의 순열은

 

(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) 총 6가지가 됩니다. 

 

(0, 1) 을 기준으로 계산을 한다고 가정하면,

 

우리는 s[0][1] + s[1][0] 과 s[2][3] + s[3][2] 의 차이를 계산해야하겠죠?

 

그렇다면 (2, 3)을 기준으로 계산 했을 때와 중복되는 계산을 하게 됩니다. 

 

때문에 중복 계산을 막기 위해 우리는 (0, 1), (0, 2), (0, 3) 기준으로만 계산을 해야하겠죠!

 

 0, 1, 2, 3 부터 시작하여 모두 dfs를 실행하면 위 6가지의 순열이 모두 탐색되지만 0부터 시작한 dfs 만 실행하면 우리가 원하는 조합을 뽑을 수 있습니다. 

 

m=n/2 길이의 조합을 뽑기 위해선 dfs에서 다음 탐색할 index 번호의 조건으로 (n-1-i) >= (m-1-depth) 를 줘야합니다. 

 

 n-1 : 숫자 배열의 마지막 index

 i : 탐색할 번호의 index

 n-1 - i : 탐색할 번호 다음에 남은 수들의 개수

 m - 1 - depth : 현재 depth 다음 depth에서 앞으로 추가해야할 수들의 개수 ( m = n/2 )

 

 arr에 m 길이의 원소가 추가 되고 나면 추가되지 않은 index 들을 arr에 추가한 뒤 calculation을 호출하여 스타트팀(0~m-1까지의 index)과 링크팀(m~n까지의 index)의 합의 차를 반환 받습니다.

 

 이 반환값을 ans와 비교하여 더 작은 값을 ans에 저장하면 됩니다. 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>

using namespace std;

int n;
int ans = 1000000000;
int s[21][21];
int arr[21];
bool visit[21] = { false, };

int calculation(int m) {
	int sum1 = 0;
	int sum2 = 0;

	for (int i = 0; i < m; i++) {
		int x = arr[i];
		for (int j = 0; j < m; j++) {
			if (i == j)
				continue;
			int y = arr[j];
			sum1 += s[x][y];
		}
	}
	for (int i = m; i < n; i++) {
		int x = arr[i];
		for (int j = m; j < n; j++) {
			if (i == j)
				continue;
			int y = arr[j];
			sum2 += s[x][y];
		}
	}

	return abs(sum1 - sum2);
}

void dfs(int idx, int depth) {
	int m = n / 2;

	if (depth == m) {
		
		for (int i = 0; i < n; i++) {
			if (!visit[i])
				arr[depth++] = i;
		}
		
		ans = min(ans, calculation(m));

		return;
	}

	for (int i = idx + 1; i < n; i++) {
		if (!visit[i] && (n - 1 - i) >= (m - 1 - depth)) {
			visit[i] = true;
			arr[depth] = i;
			dfs(i, depth + 1);
			visit[i] = false;
		}
	}
}

int main(void) {

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> s[i][j];
	}

	arr[0] = 0;
	visit[0] = true;
	dfs(0, 1);
	
	cout << ans;

	return 0;
}