[S1] 백준 14889번 스타트와 링크 C++ 백트래킹, 완전 탐색

리뷰

 

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

백트래킹 문제이나 한번 더 생각이 필요한 문제 ㅠ

 

전역 변수

• n, ans : 주어지는 팀의 개수를 저장할 변수 n, 정답을 저장할 변수 ans
• lst : 맵 정보를 입력 받을 정수형 배열, 1-based-index이므로 21 * 21로 세팅한다.
• v : 방문 처리용 배열, 크기는 20으로 초기화(?) 21로 해야하는거 같은데 20으로 했는데도 맞았다.

 

함수

1. bt

void bt(int level, vector<int>& start)

 

재귀를 통해 스타트 팀과 링크 팀의 선수 정보의 차를 구하는 함수

1. 매개변수로 재귀 단계인 level과 스타트 팀의 정보 start를 받아준다.
2. 기저조건은 총 두가지가 있다, 첫번째로 ans가 0일때는 더 이상 탐색할 필요가 없다.
3. 두번째로 level이 n / 2에 도달했다면 링크팀 정보를 받아 스타트팀과 비교를 통해 ans를 최신화 해주어야 한다.
4. 기저조건에 도달하지 않았다면 팀원 1 ~ n중 한명씩 start팀에 추가하며 재귀를 진행한다.

 

문제풀이

1. n값을 입력 받고 n * n크기의 맵에 입력값을 받아 초기화 해준다.
2. start팀 정보를 저장할 정수형 벡터 start를 초기화 하고 0과 start를 매개변수로 넣어 bt함수를 실행한다.
3. 모든 탐색을 마치고 ans에 저장된 값을 출력해 주면 된다.

 

참고 사항

start팀과 link팀을 모두 재귀를 통해 구하려고 하면 시간초과가 나게 된다.

start팀 n / 2명을 다 모집했다면 나머지 선수는 자동으로 link팀이 되니 해당 부분이 이 문제의 키포인트 인 듯 하다.

 

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;
int n, t, flag, ans = 2e9;
int lst[21][21];
int v[20];

void bt(int level, vector<int>& start) {
	if (!ans) return;
	if (level == n / 2) {
		vector<int> link;
		int start_t = 0, link_t = 0;
		for (int i = 0; i < n / 2; i++) {
			for (int j = 0; j < n / 2; j++) {
				if (i == j) continue;
				start_t += lst[start[i]][start[j]];
			}
		}
		for (int i = 1; i <= n; i++) if (!v[i]) link.push_back(i);
		for (int i = 0; i < n / 2; i++) {
			for (int j = 0; j < n / 2; j++) {
				if (i == j) continue;
				link_t += lst[link[i]][link[j]];
			}
		}
		ans = min(ans, abs(start_t - link_t));
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (v[i]) continue;
		if (!start.empty() && start.back() > i) continue;
		v[i] = 1;
		start.push_back(i);
		bt(level + 1, start);
		start.pop_back();
		v[i] = 0;
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> lst[i][j];
		}
	}
	vector<int> start;
	bt(0, start);

	cout << ans;
}