백트래킹(backtracking)

백트래킹이란 ?

• 현재 상태에서 가능한 모든 후보를 따라 들어가며 탐색하는 알고리즘

ex) 오목을 예시로 둘 수 있다. 오목을 둘 때 상대방의 바둑알을 어디에 두눈가에 따라 다양한 후보들이 생긴다.

즉 가능한 모든 경우를 생각해볼 수 있기에 이를 백트래킹 알고리즘이라고 할 수 있다.

 

알고리즘 예시1) N과 M(1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

N과 M은 전형적인 백트래킹 문제이다. 이는 1~N까지 중복 없이 M개를 선택하여 수열을 만드는 문제이다.

즉 가능한 모든 경우의 수를 check하는 알고리즘이기에 백트래킹으로 접근하여야 쉽게 풀 수 있다.

<코드>

#include <iostream>

using namespace std;
int n,m; // 사용할 숫자 1 ~ n, 출력 숫자 개수 m 
int arr[10]={0}; //출력 배열 
bool isused[10]={false};//배열이 사용되었는지 check  
void func(int k){
	if(k==m){
		for(int i=0;i<m;i++)
		{
			cout<<arr[i]<<' ';
		}
		cout<<'\n';
		return;
		//return을 만나면 함수 출력 후 다시 이전 단계로 넘어감
		//ex) func(3) => k==m이기에 배열 출력하고 
		//다시 func(2)로 돌아가게 된다. 
		//123 출력하고 func(3)으로 넘어가면 isused[3]=false가 되기에
		//124를 출력하게 된다. 
	}
	for(int i=1;i<=n;i++)
	{
		if(!isused[i]){
			arr[k]=i; //배열에 값을 대입한다.
			isused[i]=true; // i 방문했으니 값을 true로 바꿔준다.
			func(k+1); // 다음함수 호출
			isused[i]=false; // 값을 사용했으니 false로 바꿔줘야 한다.
		}
	}
	//전형적인 백트래킹 방식  
}

int main()
{
	cin>>n>>m;
	func(0);
}

예시2) N-Queen 

https://www.acmicpc.net/problem/9663

9663번: N-Queen

N-Queen 문제는 n*n 체스판에 n개의 퀸이 서로를 공격하지 못하게 배치하는 문제이다.

이 문제도 백트래킹 알고리즘으로 접근해야 한다.  각 퀸을 상하좌우, 대각선에 놓지 않으면 된다.

<코드>

#include <iostream>

int cnt = 0;
int n;
int board[15];
using namespace std;

bool check(int cur)
{
	
	for(int i=0;i<cur;i++)
	{
		if(board[cur]==board[i] || cur - i == abs(board[cur] - board[i])){
			return false;
		}
	}
	return true;
}
void nqueen(int cur)
{
	if(cur == n){
		cnt++;
		return;
	}
	for(int i=0;i<n;i++)
	{
		board[cur] = i; // cur = 행 i = 열 
		if(check(cur)){
			nqueen(cur+1);
			board[cur] = 0;
		}
	}
	
}
int main()
{
	cin>>n;
	nqueen(0);
	cout<<cnt;
}

<풀이과정>

행/열	0	1	2	3
0		●
1	●
2		●
3

다음 테이블을 봤을 때, board[cur] = board[i]는 같은 열에 존재하게 되면 false를 반환하는 코드이다. 

추가적으로, cur-i = abs(board[cur]-board[i]) 부분은 같은 대각선상에 있으면 false를 반환하는 코드이다.

예시) (1,0)에 퀸이 위치해 있을 때, (0,1) (2,1)의 퀸은 (1,0)의 퀸과 같은 대각선상에 위치하게 된다. abs(절댓값) 함수를 쓴 이유는 값이 각각의 열의 위치를 뺀 값이 음수가 되는 경우를 고려한 것이다.

nqueen 함수는 처음 시작 좌표에 퀸을 넣고, check(그 다음 퀸을 배치할 수 있는지)하고 다음 재귀함수를 호출해주는 백트래킹 방식으로 문제를 접근하였다.

 

예시3) 부분수열의 합

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

<코드>

#include <iostream>
int n, s;
int cnt=0;
int arr[1000001];
using namespace std;
void sum(int cur, int tot)
{
	if(cur == n)
	{
		if(tot == s) cnt++;
		return;
	}
	sum(cur+1,tot);
	sum(cur+1,tot+arr[cur]);
}
int main()
{
	cin>>n>>s;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	sum(0,0);
	if(s==0) cnt--;
	cout<<cnt;
}

입력,출력이 각각 다음과 같을 때를 예시로 들면,

5 0
-7 -3 -2 5 8

cur는 배열의 개수가 되고, tot는 지금까지 더해준 배열의 총합을 의미 한다.

만약 3개 -3 -2 5를 골라서 0을 만들어주면 tot == s가 되므로 개수 하나를 추가해줘야 한다.

그런데 이 문제에서 주의해야 할 점은 main문에서 s가 0이 될 때 개수 하나를 빼주는 이유는 아무런 배열을 선택하지 않았을때의 tot값이 0이 되는 경우를 제외시켜준 것이다.

<참고 자료 및 출처>

 

https://www.youtube.com/watch?v=Enz2csssTCs&t=613s