[알고리즘] 백트래킹

개념

조건을 두고 탐색을 하는 알고리즘이다. DFS와 유사한 알고리즘으로 DFS가 보든 노드를 탐색하는 알고리즘 이라면 백트래킹은 탐색에 조건을 두어 조건에 충족하지 않는 분기는 탐색을 종료하고 다음 분기로 넘어가는 알고리즘이다. 

 

모든 노드를 탐색하지 않기 때문에 특정 노드를 찾는 등의 조건이 있는 탐색이라면 당연히 DFS보다 효율적이다. 

 

백트래킹을 이미지로 나타내면 트리의 형태로 나타낼 수 있다.

 

https://www.programiz.com/dsa/backtracking-algorithm

 

 

구현

백트래킹은 조건에 따라 구현이 달라지지만 일반적으로 DFS에 조건이 추가된 형태이다.

dfs()
{
	if(조건에 충족하는가?)
    	{
    		dfs();
    	}
}

 

 

 

예제

백트래킹의 대표적인 예제로는 N-Queen문제가 있다. 

 

 

퀸은 가로, 세로, 대각선 모두 공격할 수 있는 말이다. 

따라서 여러 퀸이 서로 공격하지 못하게 놓기 위해서는 같은 행, 열에 놓여져 있으면 안 된다. 이 말은 각 행열에 하나의 퀸만 둘 수 있다는 것이기 때문에 배열의 값을 모두 다르게 하여 퀸의 위치를 1차원 배열로 나타낼 수 있다.

나같은 경우 배열의 인덱스를 행, 값을 열로 두었다.

 

가로, 세로만 생각하였을 때 퀸을 놓을 수 있는 조건이다. 

board[행] != 열

인덱스가 겹치는 일은 없기  때문에 값만 검사하면 된다.

 

두 퀸이 대각선 상에 있는 경우는 두 퀸의 행, 열의 차의 절대값이 같은 경우이다. 

abs(board[퀸1 행] - board[퀸2 행]) != abs(board[퀸1 열] - board[퀸2 열])

두 퀸이 대각선 상에 겹치기 않고 놓이는 조건이다.

 

위의 두 조건을 만족시키는 자리일 경우 퀸을 놓고 백트래킹을 이어가면 된다.

 

 

#include<iostream>
#include<cmath>
using namespace std;

int* board;
int n, cnt;

bool canSetting(int row, int col)
{
	for (int i = 0; i < row; i++)
	{
		//같은 col(세로) 또는 row와 col끼리의 차(대각선)가 같으면 퀸은 공격할 수 있음 
		if (board[i] == col || (row - i == abs(col - board[i])))
			return false;
	}

	return true;
}

void backtracking(int row)
{
	//n개의 퀸을 놓았음
	if (row == n)
	{
		cnt++;
		return;
	}

	for (int i = 0; i < n; i++)
	{
		//(row, i)자리에 퀸을 놓을 수 있는가?
		if (canSetting(row, i))
		{
			board[row] = i;//퀸을 놓고
			backtracking(row + 1);//다음 경우 탐색
		}
	}
}

int main()
{
	cnt = 0;
	cin >> n;
	board = new int[n];//index == row, value == col

	backtracking(0);

	cout << cnt;
}