[G5] 백준 15661번 링크와 스타트 C++ 백트래킹

리뷰

 

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

N명의 사람을 두 팀으로 나누어 능력치 차이의 최소값을 구하는 문제

 

 

전역 변수

• N : 배열의 최대 길이를 정의할 상수 변수
• n : 사람의 수를 저장할 변수
• ans : 정답을 저장할 변수
• lst : 인접 행렬을 저장할 배열

 

함수

1. get_stats

int get_stats(vector<int>& T) {
	int res = 0;
	for (int i : T) {
		for (int j : T) {
			res += lst[i][j];
		}
	}
	return res;
}

 

팀에 속한 인원의 능력치의 합을 구하기 위한 함수

 

2. dfs

void dfs(int level, vector<int>& S, vector<int>& L) {
	if (level == n) {
		if (S.empty() || L.empty()) return;
		int Ss = get_stats(S);
		int Ls = get_stats(L);
		if (ans > abs(Ss - Ls)) ans = abs(Ss - Ls);
		return;
	}

	S.push_back(level);
	dfs(level + 1, S, L);
	S.pop_back();

	L.push_back(level);
	dfs(level + 1, S, L);
	L.pop_back();
}

 

두 팀의 능력치의 차이의 최소값을 구하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, n*n의 lst배열에 인접 행렬을 채워준다.
2. 각 팀에 속한 사람의 번호를 저장할 벡터 S, L을 초기화 한다.
3. dfs함수에 매개변수로 재귀 단계 0, S, L을 전달하여 호출해 준다.
4. dfs함수는 매개변수로 재귀 단계를 level, 각 팀에 속한 번호 정보를 S, L로 전달 받는다.
5. level이 n에 도달한 경우 기저 조건을 수행해 준다.
6. S, L 중 빈 벡터가 있을 경우 리턴을 수행해 준다.
7. 변수 Ss, Ls에 get_stats함수에 S, L을 전달하여 각 팀의 능력치의 합을 구해준다.
8. get_stats함수는 매개변수로 각 팀에 속한 선수들의 번호가 담긴 벡터를 T로 전달 받는다.
9. 변수 res를 0으로 초기화 하고, 인접 행렬 lst를 참고하여 각 선수 번호에 해당하는 값을 res에 모두 더하고, res를 리턴해 준다.
10. ans가 Ss-Ls의 절대값 보다 크다면 ans를 Ss-Ls의 절대값으로 변경해 준다. 이후 리턴 처리해 준다.
11. 기저 조건에 해당하지 않는다면 S에 level을 추가하고, level을 증가시켜 재귀를 진행한다. 빠져나온 후엔 S에서 요소를 빼준다.
12. S측의 재귀를 모두 진행한 후엔 L의 관점에서 위 로직을 동일하게 수행해 준다.
13. 모든 재귀가 완료된 후엔 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. level에 해당하는 선수를 S팀에 넣거나 L팀에 넣는 방식의 백트래킹 방식을 사용하였다.

 

정답 코드

#include<iostream>
#include<vector>
using namespace std;

const int N = 20;
int n, ans = 2e9;
int lst[N][N];

int get_stats(vector<int>& T) {
	int res = 0;
	for (int i : T) {
		for (int j : T) {
			res += lst[i][j];
		}
	}
	return res;
}

void dfs(int level, vector<int>& S, vector<int>& L) {
	if (level == n) {
		if (S.empty() || L.empty()) return;
		int Ss = get_stats(S);
		int Ls = get_stats(L);
		if (ans > abs(Ss - Ls)) ans = abs(Ss - Ls);
		return;
	}

	S.push_back(level);
	dfs(level + 1, S, L);
	S.pop_back();

	L.push_back(level);
	dfs(level + 1, S, L);
	L.pop_back();
}

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

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

	vector<int> S, L;
	dfs(0, S, L);
	cout << ans;
}