백트래킹

백트래킹(BackTracking)이란 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아가는 알고리즘을 말한다.

모든 노드를 탐색하는 DFS와 비슷하지만 특정 조건인 유망성 검사(Promising)를 만족하지 않는 경우 바로 이전 단계로 돌아가서 다른 경로를 탐색한다.

이것을 가지치기(Pruning)라고 한다.

• 유망성 검사 (Promising) 이 경로가 해가 될 것인지 안될 것인지를 판단함. Promising 하다면 계속 진행하고, NonPromising 하다면 그 경로는 끝까지 갈 필요가 없으므로 다시 되돌아간다.
• 가지치기 (Pruning) 유망성 검사를해서 NonPromising 하다면 현재 경로를 포기하고 다른 경로를 탐색함.

실제 구현시 재귀를 이용하는 경우가 많으며, 고려할 수 있는 모든 경우의 수를 상태 공간 트리를 통해 표현한다. (반드시 트리 형태일 필요는 없다.)

예시

N 과 M

자연수 N, M 이 주어질 때 1 부터 N 까지의 자연수 중 중복없이 선택하여 길이가 M 인 수열을 모두 구하시오.

#include <iostream>
#include <vector>

int N, M;
std::vector<int> Nums; // 조건을 만족하는 수를 저장함
std::vector<bool> bUsed; // 숫자의 사용 여부를 저장함

void FindFunc(int Count)
{
	// Find
	if (Count == M)
	{
		for (int i = 0; i < M; i++)
			std::cout << Nums[i] << " ";
		std::cout << "\\n";
		return;
	}

	// BackTracking
	for (int i = 1; i <= N; ++i)
	{
		// Promising & Pruning
		if (!bUsed[i])
		{
			Nums[Count] = i;
			bUsed[i] = true;
			FindFunc(Count + 1);
			bUsed[i] = false;
		}
	}
}

int main()
{
	N = 4, M = 2;
	Nums.resize(N, 0);
	bUsed.resize(N + 1, false);
	FindFunc(0);
	return 0;
}

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

N-Queen 문제

N * N 체스판에 N 개의 퀸을 놓을 때 서로가 공격을 하지 못하게 만들 수 있는 경우의 수

• 퀸이 서로 공격을 하지 못하려면, 같은 가로, 세로, 대각선 상에 있으면 안된다. (Promising)
• 백트래킹을 이용해서 모든 경우의 수를 계산, NonPromising 일시 가지치기한다.

#include <iostream>
#include <vector>

bool Promising(const std::vector<int>& Board, int Row, int Col)
{
	for (int i = 0; i < Row; ++i)
	{
		if (Board[i] == Col || std::abs(Board[i] - Col) == Row - i)
			return false;
	}

	return true;
}

void N_Queen(std::vector<int>& Board, int Row)
{
	int N = Board.size();
	
	// Find
	if (Row == N)
	{
		for (int Row = 0; Row < N; ++Row)
		{
			for (int Col = 0; Col < N; ++Col)
			{
				if (Board[Row] == Col)
					std::cout << "Q";
				else
					std::cout << ".";
			}
			std::cout << "\\n";
		}
		std::cout << "\\n";
	}

	// BackTracking
	for (int Col = 0; Col < N; ++Col)
	{
		// Promising & Pruning
		if (Promising(Board, Row, Col))
		{
			Board[Row] = Col;
			N_Queen(Board, Row + 1);
			Board[Row] = -1;
		}
	}
}

int main()
{
	int N = 4;
	std::vector<int> Board(N, -1); // 각 행에 있는 퀸의 위치를 저장
	N_Queen(Board, 0);
	return 0;
}

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..