백준 15661 링크와 스타트 c++ (완전탐색)

문제 출처 : https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이다. 이제 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

알고리즘 분류

• 브루트포스 알고리즘

풀이

이리 보고 저리 봐도 완전 탐색에 근거한 조합 문제이다.

하지만 문제의 입력은 20이고, 모든 경우를 탐색하면 20C1, 20C2, ~~~ ,20C20까지 구해야 하고,

구한 조합들에 대해 또, 두 팀의 능력치를 구해야 하기 때문에 모든 경우를 탐색하면 무조건 시간 초과이다.

따라서, 우리는 탐색할 범위를 줄이거나, 가지치기를 해야 할 것을 생각할 수 있다.

한 팀이 정해지면, 다른 한 팀은 자동으로 남은 사람들끼리 팀이 구성되므로, 탐색할 범위를 줄일 수 있을 것 같다.

bool[20] 배열을 두고, 조합 알고리즘을 통해, 한 팀의 조합을 true로 표현하면, 나머지 false가 나머지 팀이 된다.

여기서 핵심은,

팀1이 1,3,5이고, 팀2가 2,4,6인 경우와,

팀1이 2,4,6이고, 팀2가 1,3,5인 경우, 

두 팀의 능력치 차이가 같다는 것이다.

우리는 조합 알고리즘을 통해 팀1의 조합을 구하는데, 1,3,5를 구했으면 2,4,6은 구하지 않아도 된다는 뜻이다.

아래의 코드들이 위의 경우를 모두 건너뛰진 않지만, 위의 경우를 감안하고 코드를 짜면, 시간 복잡도를 줄일 수 있다.

1번 코드는 for문을 쓰지 않는 대신, 한 뎁스마다 현재 선수를 true,false처리 후 다음 뎁스로 넘어가서 재귀 호출을 줄였다.

2번 코드는 for문을 쓰지만, 인원이 8명이라고 할 때, 팀1의 선수들을 1명부터 4명까지 모두 뽑았다면, 5~8명은 뽑을 필요가 없으니 n/2까지만 for문을 돌렸다. 

완벽히 검사해야 할 조합만 검사한 경우 또는 더 좋은 풀이가 있으면 코멘트 바랍니다!!!

코드2에서 if(cnt>n/2) return 일 때 (통과)

코드2에서 if(cnt>n) return 일 때(시간 초과)

코드1 (통과)

코드1

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;


int n;
int graph[20][20];
bool visited[20];
int pairs[2];
int answer = 987654321;

int cal() {
	int cnt1 = 0;
	int cnt2 = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			if (visited[i] && visited[j]) {
				cnt1 += graph[i][j] + graph[j][i];
			}
			else if (!visited[i] && !visited[j]) {
				cnt2 += graph[i][j] + graph[j][i];
			}
		}
	}
	return abs(cnt1 - cnt2);
}

void combination(int cnt) {
	if (cnt == n) {
		//팀 비교
		answer =min(answer,cal());
		return;
	}
		visited[cnt] = true;
		combination(cnt + 1);
		visited[cnt] = false;
		combination(cnt + 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

	combination(0);
	cout << answer;
	return 0;
}

코드2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int n;
int graph[20][20];
bool visited[20];
int pairs[2];
int answer = 987654321;
int cal() {
	int cnt1 = 0;
	int cnt2 = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			if (visited[i] && visited[j]) {
				cnt1 += graph[i][j] + graph[j][i];
			}
			else if (!visited[i] && !visited[j]) {
				cnt2 += graph[i][j] + graph[j][i];
			}
		}
	}
	return abs(cnt1 - cnt2);
}
void combination(int cnt, int idx) {
	if (cnt > n / 2) {
		return;
	}
	if (cnt > 0) {
		//팀 비교
			answer = min(cal(), answer);
		
	}
	for (int i = idx; i < n; i++) {
		visited[i] = true;
		combination(cnt + 1, i + 1);
		visited[i] = false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

	combination(0, 0);
	cout << answer;
	return 0;
}