[C++]-백트래킹(Backtracking)이란? + n-Queens문제

Backtracking

• 되추적 알고리즘이라고 한다.
• 결과를 찾는 도중 막히면 다시 되돌아가서 다시 결과를 찾음.
• 모든 노드를 탐색해서 만드는 DFS와 비슷하다.

DFS vs Backtracking

• DFS는 모든 노드를 탐색한다.
• Backtracking은 모든 노드를 탐색하지만, 특정 조건을 설정해서 이 경로가 해가 안될 거라고 판단이 되면 경로를 이탈하고 다시 되돌아간다.

--> 이것을 가지치기라고 한다.

• 가지치기를 통해서 불필요한 경로를 차단해서 효율성을 높일 수 있다.

 

Promising

• 유망성 검사 - 이 경로가 특정조건을 걸어서 해가 될 것인지 안될 것인지 판단함.
• nonpromising 하다면, 그 경로는 끝까지 갈 필요가 없으므로, 다시 되돌아감.
• promising 하다면 계속 진행함.

Pruning

• 가지치기- 유망성 검사를 해서 nonpromising 하다면 과감하게 진행하는 것을 포기하고 다른 경로를 탐색함.

예시

1.N-Queen

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

설계

• 퀸이 서로 공격을 하지 못할려면, 같은 가로, 세로, 대각선 상에 있으면 안 된다.(Promising)
• Backtracking을 이용해서 모든 경우의 수를 계산하는데 서로가 공격하는 조건을 만족 시에 가지치기를 함.
• 만약 퀸의 수가 N이면 경우의 수 하나를 더해줌.
• 배열을 하나 만들어서 가로, 세로 중 하나를 고정시켜줌.

ex) visit [N+1]에서 index값을 가로, 세로 중 하나로 지정해두고, 그 index안에 들어가는 value를 그 때의 좌표(가로or세로)라고 생각하면 편하다. 설명할 때는 visit배열에 index를 가로라고 지정하고 그 안에 value를 세로라고 가정하겠다.

• 가로,세로중 하나를 고정해두면 Promising을 해야 하는 경우의 수가 하나 줄어든다.

Promising 조건

1. visit배열에서 서로 다른 값을 가져야 한다. 같은 값의 의미는 같은 세로상에 위치한다는 뜻이다.
2. 같은 대각선이라는 것을 판단하려면 아래 설명을 이용하겠다. (말로 하면 어려워서..ㅎㅎ)

위의 그림은 같은 대각선 상에 있는 경우이다.

visit={1,2}이다. 즉 visit [1]=1, visit [2]=2이다.(배열 visit은 1번지부터 시작한다는 가정을 하겠다.)

3번의 값은 index값의 차이이다. 4번의 값은 index안에 value값의 차이이다.

즉 서로 비교하려는 퀸들의 index값의 차이와 index안에 value값의 차이가 같을 때 같은 대각선 상에 있다고 볼 수 있고,

모든 방향을 검사하려면 절댓값을 씌어주면 된다.

위 그림은 같은 대각선이 아닐 때이다.

visit [1]=1, visit [2]=3이다. 

3번과 4번의 값은 일치하지 않는다. 따라서 같은 대각선 상에 있지 않다.

 

유망도 검사 코드

visit[i]==visit[k] //같은 세로일때

abs(i-k)==abs(visit[i]-visit[k]) //같은 대각선일 때

 

전체 코드

#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
using namespace std;
int n;
vector<int>board;
void n_queen(int i);
bool promising(int i);
unsigned long long sum = 0,Max=0;
string a = "";
int main()
{
	cin >> n; //보드 크기
	board.resize(n+1);
    n_queen(0);
	cout << sum << endl<<Max;
}
void n_queen(int i)
{
	if (promising(i)==1) //promising이 1이면 안짜르고 0이면 가지치기
	{
		if (i == n) // 끝까지 다 검사햇다는 뜻
		{
			for (int i = 1; i < board.size(); i++)
			{
				a += to_string(board[i]);
				//cout << board[i] << " ";
				//board[i]를 string에 넣어서 
			}
			//cout << a << endl;
			long long int temp = stoll(a); //문자열을 long long 으로 바꿈
			if (Max < temp)
				Max = temp;
			a = "";
			sum++;
		}
		else
			for (int j = 1; j <= n; j++)
			{
				board[i + 1] = j;
				n_queen(i + 1);
			}
	}
}
bool promising(int i) //promising 할떄 가지치기해야함.
{
	int idx = 1;
	bool flag = true;
	while (idx < i && flag) // idx가 넘지 않을 때 까지 반복, 그리고 참인값을 찾으면 promising 종료
	{
		if (board[i] == board[idx] || abs(board[i] - board[idx]) == abs(i - idx)) //같은열과 대각선 전부다 제외
		{
			flag = false;
		}
		idx++;
	}
	return flag;
}

 

함수 n_queen에서 if(i==N)일 때의 내용을 각자 문제 조건에 맞춰서 바꾸면 해결할 수 있을 것입니다.

 

출처:대학교 강의자료, 알고리즘 기초