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

문제

14889번: 스타트와 링크

이 문제의 관건은 팀을 2개로 나누는 여러가지 조합에대해서 처리해주어야하는 것입니다.

여기서 포인트는 중복이 아니라 조합이라는 것입니다.

1, 2, 3, 4 중에서 start 팀 = (1, 2)  link 팀 =(3, 4) 과 start 팀 = (3, 4), link 팀 =(1, 2) 는 2가지가 아니라 1가지로

취급하는 것입니다.

int n;
int arr[21][21];
bool check[21];
int ans = INT_MAX;
void dfs(int cur, int next);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}

arr은 배열을 받고, 변수 ans는 두 팀의 능력치의 차의 최솟값을 넣을 것입니다. 

check 배열은 dfs를 실행할 때 방문한곳을 체크하기 위함입니다.

void dfs(int cur, int next) {
	if (cur == n / 2) {
		int start = 0;
		int link = 0;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (check[i] == true && check[j] == true)start += arr[i][j];
				if (check[i] == false && check[j] == false)link += arr[i][j];
			}
		}
		int temp = abs(start - link);
		if (ans > temp)ans = temp;

		return;
	}

	for (int i = next; i < n; i++) {
		check[i] = true;
		dfs(cur + 1, i + 1);
		check[i] = false;
	}
}

main 함수에서 dfs(0, 1)을 호출합니다. 변수 cur는 지금까지 뽑은 팀원의 수 입니다. 

변수 next는 현재 check 배열에서 뽑을 인덱스 위치 입니다. 

4개의 팀원이 있으면 2명이 팀이 되면 자동적으로 팀이 구성되므로 cur이 n/2 가 되면 본격적으로 계산을 진행합니다.

for (int i = next; i < n; i++) {
	check[i] = true;
	dfs(cur + 1, i + 1);
	check[i] = false;
}

dfs 함수 마지막에 있는 부분입니다. 

여기서 for문을 i<n까지로 설정했는데 이렇게 설정하게 되면

1, 2, 3, 4 중에서

{1, 2}

{1, 3}

{2, 3}

만을 탐색하게 됩니다.

이렇게 되면 

start          /       link

{1, 2}                 {3, 4}

{1, 3}                 {2, 4}

{2, 3}                 {1, 4}

가 자동적으로 완성하게 됩니다. 

 

반면에 for문을 i<=n 까지로 설정하면

1, 2, 3, 4 중에

{1, 2}

{1, 3}

{1, 4}

{2, 3}

{2, 4}

{3, 4}

까지 모두 탐색하게 됩니다.

이렇게 되면

start            /     link

{1, 2}                 {3, 4}

{1, 3}                 {2, 4}

{1, 4}                 {2, 3}

{2, 3}                 {2, 4}

{2, 4}                 {1, 3}

{3, 4}                 {1, 2}

중복이 발생하게 됩니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n;
int arr[21][21];
bool check[21];
int ans = INT_MAX;
void dfs(int cur, int next);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}
	dfs(0, 1);

	cout << ans;
	return 0;
}
void dfs(int cur, int next) {
	if (cur == n / 2) {
		int start = 0;
		int link = 0;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (check[i] == true && check[j] == true)start += arr[i][j];
				if (check[i] == false && check[j] == false)link += arr[i][j];
			}
		}
		int temp = abs(start - link);
		if (ans > temp)ans = temp;

		return;
	}

	for (int i = next; i < n; i++) {
		check[i] = true;
		dfs(cur + 1, i + 1);
		check[i] = false;
	}
}