완전탐색과 백트래킹 c++ 설명

완전 탐색

완전 탐색은 말 그대로 모든 경우의 수를 탐색하는 방법으로 브루트 포스라고 불린다(brute-force)

완전 탐색의 방법은 반복문과 재귀함수로 나뉜다.

 

반복문

반복문으로 가능하다면 반복문으로 하는 것이 좋다.

 

재귀함수

너무 복잡하거나 어떠한 행위는 반복하는데 매개변수만 수정해서 넘기면 될 것 같은 경우에 시행한다.

 

 

 

예시 문제

100이하의 수 조합이 주어질 때 소수가 되는 경우의 수를 모두 구하여라

 

입력예시:

10

24 35 38 40 49 59 60 67 83 98

 

코드 구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
vector<int> v;
vector<int> s;

bool isPrime(int n) {
	if (n == 0)
		return false;
	for (int i = 2; i < n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}


int go(int idx, int sum, int n) {
	if (idx == n)
		return isPrime(sum);

	return go(idx + 1, sum+v[idx], n) + go(idx + 1, sum, n);
}



int main() {
	int n, num;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
	}
	cout<< go(0, 0, n);
	
}
/*
10
24 35 38 40 49 59 60 67 83 98
*/

 

 

예시문제

N과 N개의 자연수가 주어진다. 

여기서 몇개의 숫자를 골라 합을 mod11을 했을 때 나오는 가장 큰수를 구하라.

 

입력예시:

10

24 35 38 40 49 59 60 67 83 98

코드구현

#include <iostream>
#include<iostream>
#include <vector>
#include <algorithm>
#include<math.h>

using namespace std;


vector<int> v;
int N, ret = 0;
void BigSearch(int sum, int idx) {
	if (idx == N)
	{
		ret = max(ret, sum%11 );
		return;
	}
	BigSearch(sum + v[idx], idx + 1);
	BigSearch(sum, idx + 1);
}

int main() {
	int num;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		v.push_back(num);
	}
	BigSearch(0, 0);
	cout << ret;
	
}
/*
10
24 35 38 40 49 59 60 67 83 98

*/

 

백트래킹

완전탐색에 가지치기를 더해 불필요한 탐색을 최소화 시킨 것을 말한다.

또한 dfs의 변형적인 형태로 가지치기를 추가했다고 볼 수 있다.

 

아까의 그 코드를 다시 살펴보자

#include <iostream>
#include<iostream>
#include <vector>
#include <algorithm>
#include<math.h>

using namespace std;


vector<int> v;
int N, ret = 0, cnt=0;
void BigSearch(int sum, int idx) {
	if (idx == N)
	{
		ret = max(ret, sum%11 );
		cnt++;
		return;
	}
	BigSearch(sum + v[idx], idx + 1);
	BigSearch(sum, idx + 1);
}

int main() {
	int num;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		v.push_back(num);
	}
	BigSearch(0, 0);
	cout << ret<<"\n";
	cout << cnt;
}
/*
10
24 35 38 40 49 59 60 67 83 98
*/

 

출력이 10 1024가 나오는 것을 볼 수 있다. 즉 2의 10승 번 탐색을 진행한 것이다.

그렇다면 이것을 어떻게 가지치기 할 수 있을까?

 

 

바로  mod의 성질을 이용하는 것이다. mod11을 했을 때 최대로 나올 수 있는 것은 10이다.

그때 탐색을 종료시켜 주면 된다.

 

#include <iostream>
#include<iostream>
#include <vector>
#include <algorithm>
#include<math.h>

using namespace std;


vector<int> v;
int N, ret = 0, cnt=0;
void BigSearch(int sum, int idx) {
	if (ret == 10)
		return;
	if (idx == N)
	{
		ret = max(ret, sum%11 );
		cnt++;
		
		return;
	}
	BigSearch(sum + v[idx], idx + 1);
	BigSearch(sum, idx + 1);
}

int main() {
	int num;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		v.push_back(num);
	}
	BigSearch(0, 0);
	cout << ret<<"\n";
	cout << cnt;
}
/*
10
24 35 38 40 49 59 60 67 83 98

*/

 

이렇게 하면 탐색 수가 10으로 줄어든 것을 볼 수 있다.

 

 

 

++완전 탐색 원상 복구

모든 경우의 수를 탐색하는 경우 다시 미방문 처리하고 탐색해야 하는 경우가 있다.

 

예시 문제

나는 3*3맵에서 0,0 지점에 있다. 목적지는 2,2인데 가는 길에 점수를 얻는다. 점수를 얻는 모든 경우의 수를 구해라

 

맵:

{10, 20, 21},

{70, 90, 12},

{80, 110, 120}

 

 

코드 구현

#include <iostream>
#include<iostream>
#include <vector>
#include <algorithm>
#include<math.h>

using namespace std;


vector<int> v;

const int n = 3;
int visit[3][3] = { 0 };
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int board[3][3] = {
	{10, 20, 21},{70, 90, 12},{80, 110, 120}
};


void dfs(int x, int y) {
	if (x == 2 && y == 2)  //도착한 경우 출력
	{
		for (int i : v)
			cout << i << " ";
		cout << "\n";
		return;  //기저사례
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx > 3 || ny < 0 || ny > 3)
			continue;
		if (visit[ny][nx])
			continue;
		v.push_back(board[ny][nx]);
		visit[ny][nx] = 1;
		dfs(nx, ny);
        //다시 원상복구
        
		v.pop_back();   
		visit[ny][nx] = 0;
	}
}

int main() {
	dfs(0, 0);
}