백트래킹 (Backtracking)

백트래킹이란 경로를 탐색하다가 올바르지 않은 경로라면 계속해서 탐색하는 것이 아니라 이전 단계로 돌아가 다시 올바른 경로를 향해 찾아가는 알고리즘이다.

 

모든 경로를 탐색하는 알고리즘인 DFS를 이용하지만, 조건에 맞지 않는 경로는 제외시킨다는 점에서 조금 더 효율적이다. 여기서 경로를 제외시키는 것을 가지치지(pruning)이라고 한다. 가지치기를 하기 위한 조건을 얼마나 잘 설정하느냐에 따라 시간복잡도가 천차만별이다.

 

백트래킹 알고리즘은 대표적으로 순열, 조합을 구하는 것에 이용된다. 

1. 순열 (중복x)

● 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <random>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int N, M;
vector<int>arr;
vector<int>visit(9);
void DFS(int cnt)
{
	if (cnt == M)
	{
		for (int i = 0; i < arr.size(); i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = 1; i <= N; i++)
	{
		if (visit[i] == 0)
		{
			visit[i] = 1;
			arr.push_back(i);
			DFS(cnt + 1);
			visit[i] = 0;
			arr.pop_back();
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	DFS(0);
	return 0;
}

● 결과 화면

● 시간복잡도 : N!

● BOJ 문제 : 15649 N과 M (1)

15649번: N과 M (1)

 

2. 조합 (중복x)

● 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <random>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int N, M;
vector<int>arr;
vector<int>visit(9);
void DFS(int start, int cnt)
{
	if (cnt == M)
	{
		for (int i = 0; i < arr.size(); i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = start; i <= N; i++)
	{
		if (visit[i] == 0)
		{
			visit[i] = 1;
			arr.push_back(i);
			DFS(i + 1, cnt + 1);
			visit[i] = 0;
			arr.pop_back();
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	DFS(1, 0);
	return 0;
}

● 결과 화면

● 시간복잡도 : N!

● BOJ 문제 : 15650 N과 M (2)

15650번: N과 M (2)

 

3. 순열 (중복o)

● 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <random>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int N, M;
vector<int>arr;
vector<int>visit(9);
void DFS(int cnt)
{
	if (cnt == M)
	{
		for (int i = 0; i < arr.size(); i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = 1; i <= N; i++)
	{
		visit[i] = 1;
		arr.push_back(i);
		DFS(cnt + 1);
		visit[i] = 0;
		arr.pop_back();
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	DFS(0);
	return 0;
}

● 결과 화면

● 시간복잡도 : N!

● BOJ 문제 : 15651 N과 M (3)

15651번: N과 M (3)

 

4. 조합 (중복o)

● 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <random>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int N, M;
vector<int>arr;
vector<int>visit(9);
void DFS(int start, int cnt)
{
	if (cnt == M)
	{
		for (int i = 0; i < arr.size(); i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = start; i <= N; i++)
	{
		visit[i] = 1;
		arr.push_back(i);
		DFS(i, cnt + 1);
		visit[i] = 0;
		arr.pop_back();
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	DFS(1, 0);
	return 0;
}

● 결과 화면

● 시간복잡도 : N!

● BOJ 문제 : 15652 N과 M (4)

15652번: N과 M (4)