[알고리즘/문제풀이/BOJ 14889번/삼성 SW 역량 테스트 기출] 스타트와 링크

스타트와 링크 문제는 N명의 사람들을 두 집합으로 나누고 각 집합별로 능력치 합을 구하여 가장 적은 집합 간의 능력치 합의 차를 출력하는 문제입니다.

집합을 나누는 데 모든 가능한 경우의 수를 탐색하기 위해 백트래킹 기법을 사용하였습니다. 이때 주의해야 할 점은 자칫 똑같은 집합을 두 번 중복하여 계산할 수 있다는 점입니다. A집합에 있는 원소들이 그대로 B집합에 있는 상황입니다. 이러한 불필요한 연산을 방지하기 위해서는 어느 특정한 원소를 특정한 집합에만 존재한다고 미리 가정하여야 합니다.

예로 들어서 1을 기준으로 둘 때 모든 경우는 1을 포함한 집합과 포함하지 않는 집합으로 이루어져 있다는 것을 확인할 수 있습니다. 이때 1이 A집합에만 존재한다고 가정하면 똑같은 원소의 종류로 분할된 상황에서 B집합에 1이 있는 경우를 배제하여 똑같은 경우를 2번 반복하여 연산하는 상황을 예방할 수 있습니다.

집합을 나눈 후 능력치의 합을 구할 때는 순열을 사용하여 계산할 수 있습니다. 그렇게 하여 각 집합의 모든 능력치의 합을 계산하여 그 값들의 차 중 가장 적은 값을 출력함으로써 문제를 해결할 수 있습니다.

필자가 작성한 코드는 다음과 같습니다.

---

#include<stdio.h>
#include<math.h>
//https://ark-hive.tistory.com/

int N;
int S[30][30];
int Ateam[30];
int Bteam[30];
int temp[30];
int sum1, sum2;
int min = 123456789;

//중복없이 집합 내 조합을 유지하기 위해서는 오름차순 유지
//조합은 순열의 정렬로

//필요없는 경우를 제외해야 함.(두 집합 사이에서 원소만 그대로 바뀐 상황)
//팀 가르기이므로 어느 집합 하나에는 특정 수가 반드시 있어야 함.
//집합의 이름만 다르고 원소의 종류는 같은 경우가 있을 수 있음.
//이때 특정 임의의 수가 특정 한쪽 집합에만 존재할 수 있다고 하면.(고정)
//그러한 모든 원소가 뒤바뀐 상황을 제거할 수 있다.

void final_processing() {
	sum1 = 0;
	sum2 = 0;

	for (int i = 0; i < N/2; i++) {
		for (int j = 0; j < N/2; j++) {
			if (i == j) continue;
			sum1 += S[Ateam[i]][Ateam[j]];
			sum2 += S[Bteam[i]][Bteam[j]];
		}
	}
	if (min > abs(sum1 - sum2))
		min = abs(sum1 - sum2);

	return;
}

void backtracking(int order) {
	//1을 기준으로 삼음.
	if (order == N/2-1) {
		for (int i = 1; i <= N; i++) {
			temp[i] = 0;
		}
		for (int i = 0; i < N/2; i++) {
			temp[Ateam[i]]=1;
		}
		for (int i = 1, j=0; i <= N; i++) {
			if (temp[i] == 0) {
				Bteam[j]=i;
				j++;
			}
		}
		final_processing();
		//가능한 순열 모두 찾기
		return;
	}
	else {
		for (int i = Ateam[order]+1; i <= N; i++) {
			Ateam[order + 1] = i;
			backtracking(order + 1);
			Ateam[order + 1] = 0;
		}
	}
}

int main(void) {
	scanf("%d", &N);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &S[i][j]);
		}
	}

	Ateam[0] = 1;
	backtracking(0); //A 집합에서 0명을 골랐다.
	printf("%d\n", min);
}

문제의 지문은 다음의 링크에서 확인할 수 있습니다.

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