백트래킹 C++

개요

백트래킹 : 재귀 호출 중 가망성이 있는지 여부를 판별하면서 진행하는 방식

재귀를 통해 경우의 수를 모두 탐색하여 구하고자 하는 조건에 일치하는 경우를 모두 구할 수 있다.

실행하고자 하는 하는 반복 횟수, 재귀를 빠져나올 기저 조건, 각 반복 횟수에 적용할 식을 잘 세우면 효율적으로 사용할 수 있다.

 

 

예제

1. 조합을 선택하여 출력하기

서로 다른 n개의 수에서 k개의 수로 이루어진 조합을 출력하기

코드

#include <iostream>

using namespace std;

int n, k;
int arr[100];
int DAT[110];

void bt(int index) {
	// 2. 기저 조건
	if (index >= k) {
		for (int i = 0; i < k; i++) {
			cout << DAT[i] << " ";
		}
		cout << "\n";
		return;
	}

	// 1. 재귀 기본
	for (int i = 0; i < n; i++) {
		// 3-1. 앞으로 진행되면서 실행되는 코드
		DAT[index] = arr[i];
		bt(index + 1);
		DAT[index] = 0;
	}
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	bt(0);
}

 

입력

4 3
1 2 3 4

 

출력

1 1 1
1 1 2
1 1 3
...
4 4 2
4 4 3
4 4 4

 

2. 조합을 선택하여 출력하고, 해당 조합의 합 구하기

코드 (매개 변수가 아닌 전역 변수를 사용해 주어도 된다.)

#include <iostream>

using namespace std;

int n, k;
int arr[100];
int DAT[110];

void bt(int index, int sum) {
	// 2. 기저 조건
	if (index >= k) {
		for (int i = 0; i < k; i++) {
			cout << DAT[i] << " ";
		}
		cout << "= " << sum << "\n";
		return;
	}

	// 1. 재귀 기본
	for (int i = 0; i < n; i++) {
		// 3-1. 앞으로 진행되면서 실행되는 코드
		DAT[index] = arr[i];
		sum += arr[i];
		bt(index + 1, sum);
		DAT[index] = 0;
		sum -= arr[i];
	}
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	bt(0, 0);
}

 

입력

4 3
1 2 3 4

 

출력

1 1 1 = 3
1 1 2 = 4
1 1 3 = 5
...
4 4 2 = 10
4 4 3 = 11
4 4 4 = 12

 

3. 인접한 값과 차이가 1이 아닌 경우만 조합하여 출력하기

코드

#include <iostream>

using namespace std;

int n, k;
int arr[100];
int DAT[110];

void bt(int index, int before) {
	if (index >= k) {
		for (int i = 0; i < k; i++) {
			cout << DAT[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = 0; i < n; i++) {
		if (abs(arr[i] - before) != 1) { // 판별식 추가
			DAT[index] = arr[i];
			bt(index + 1, arr[i]);
			DAT[index] = 0;
		}
	}
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	bt(0, -1);
}

 

입력

4 3
1 2 3 4

 

출력

1 1 1
1 1 3
1 1 4
...
4 4 1
4 4 2
4 4 4

 

 

 

 

 

 

 

 

실습

3. N개의 주사위를 던져 중복되지 않는 조합 출력하기

최대 6개의 주사위를 던져 중복되지 않는 모든 조합을 찾아보자(1, 2, 3, 4, 5와 5, 4, 3, 2, 1은 인정되는 조합)

코드

#include <iostream>

using namespace std;

int n, k;
int DAT[6];
int v[7];

void bt(int index) {
	if (index >= n) {
		for (int i = 0; i < n; i++) {
			cout << DAT[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = 1; i <= 6; i++) {
		if (!v[i]) {
			DAT[index] = i;
			v[i] = 1;
			bt(index + 1);
			DAT[index] = 0;
			v[i] = 0;
		}
	}
}

int main() {
	cin >> n;
	bt(0);
}

 

입력

6

 

출력

1 2 3 4 5 6
1 2 3 4 6 5
1 2 3 5 4 6
...
6 5 4 2 3 1
6 5 4 3 1 2
6 5 4 3 2 1